MenuItem style with icon creates only one icon

Add x:Shared=false for your Icon value. To do that you should declare Image in resources:

<Grid>
  <Grid.Resources>

   <Image x:Key="imgCTX" x:Shared="false"
         Source="{Binding Path=Icon}" Height="16px" Width="16px"/>
    <HierarchicalDataTemplate DataType="{x:Type ViewModels:HeaderedItemViewModel}"
        ItemsSource="{Binding Path=Children}">
      <ContentPresenter RecognizesAccessKey="True"></ContentPresenter>
    </HierarchicalDataTemplate>
    <Style TargetType="{x:Type MenuItem}">
      <Setter Property="Header" Value="{Binding Path=Header}" />
      <Setter Property="InputGestureText" Value="{Binding Path=InputGestureText}" />
      <Setter Property="Command" Value="{Binding Path=Command}" />
      <Setter Property="Icon" Value="{StaticResource imgCTX}" />
    </Style>
  </Grid.Resources>
  <Menu Grid.Row="0" ItemsSource="{Binding Path=Shell.Navigation.Menus}" />
</Grid>