Using a DataTemplate for a MenuItem causes extra space on the left side to appear?

It's because the visual tree produced by your DataTemplate will be wrapped in a container - in this case, a MenuItem. Therefore, you actually have a MenuItem within a MenuItem, which explains the extra space and the lack of interactivity. There's no need to include the MenuItem in your ItemTemplate.

Your example might instead be written as:

<Menu>    <MenuItem Header="Enemies" ItemsSource="{Binding AvailableEnemyClasses}">        <MenuItem.ItemTemplate>            <DataTemplate>                <TextBlock Text="{Binding}"/>            </DataTemplate>        </MenuItem.ItemTemplate>    </MenuItem></Menu>

Or, perhaps more succinctly:

<Menu>    <MenuItem Header="Enemies" ItemsSource="{Binding AvailableEnemyClasses}">        <MenuItem.ItemContainerStyle>            <Style TargetType="MenuItem">                <Setter Property="Header" Value="{Binding}"/>                <Setter Property="IsChecked">                    <Setter.Value>                        <MultiBinding Converter="{StaticResource YourConverter}">                            <Binding .../>                            <Binding .../>                        </MultiBinding>                    </Setter.Value>                </Setter>            </Style>        </MenuItem.ItemContainerStyle>    </MenuItem></Menu>