Placing a programatically created menu
After an intensive debug session I discovered the block is actually created when you place blocks and select the menu you have just created through the Block UI. That didn't fit with my requirements to place the block programatically so I took a look at the structure of an existing menu block and replicated that.
$this-&gt;block = $this-&gt;entityTypeManager-&gt;getStorage('block')-&gt;create(
    [
      'id' =&gt; $this-&gt;getBid($form_state-&gt;getValue('language')),
      'region' =&gt; 'header',
      'plugin' =&gt; 'system_menu_block:' . $this-&gt;menu-&gt;id(),
      'settings' =&gt; [
        'id' =&gt; 'system_menu_block:' . $this-&gt;menu-&gt;id(),
        'label' =&gt; $this-&gt;menu-&gt;label(),
        'provider' =&gt; 'system',
        'level' =&gt; 1,
        'depth' =&gt; 0,
        'expand_all_items' =&gt; FALSE,
      ],
      'theme' =&gt; 'mytheme_base_theme',
      'visibility' =&gt; [
        'language' =&gt; [
          'id' =&gt; 'language',
          'langcodes' =&gt; [
            $form_state-&gt;getValue('language') =&gt; $form_state-&gt;getValue('language'),
          ],
          'negate' =&gt; FALSE,
          'context_mapping' =&gt; [
            'language' =&gt; '@language.current_language_context:language_interface',
          ],
        ],
      ],
      'weight' =&gt; 100,
    ]
  );
  // Save the block.
  $this-&gt;block-&gt;save();

This achieved the result I was looking for. So far so good. I can now create menus and place them immediately after the menu is created.