How to Display Working Keyboard Shortcut for Menu Items?

Question 1

I'll start with the warning. It can happen that you will need not only customizable hot keys but the menu itself. So think twice before using InputBindings statically.
There is one more caution concerning InputBindings: they imply that command is tied to the element in window's visual tree. Sometimes you need global hot keys not connected with any particular window.

The above said means that you can make it another way and implement your own application wide gestures processing with correct routing to corresponding commands (don't forget to use weak references to commands).

Nonetheless the idea of gesture aware commands is the same.

public class CommandWithHotkey : ICommand
{
    public bool CanExecute(object parameter)
    {
        return true;
    }

    public void Execute(object parameter)
    {
        MessageBox.Show("It Worked!");
    }

    public KeyGesture Gesture { get; set; }

    public string GestureText
    {
        get { return Gesture.GetDisplayStringForCulture(CultureInfo.CurrentUICulture); }
    }

    public string Text { get; set; }

    public event EventHandler CanExecuteChanged;

    public CommandWithHotkey()
    {
        Text = "Execute Me";

        Gesture = new KeyGesture(Key.K, ModifierKeys.Control);
    }
}

Simple View Model:

public class ViewModel
{
    public ICommand Command { get; set; }

    public ViewModel()
    {
        Command = new CommandWithHotkey();
    }
}

Window:

<Window x:Class="CommandsWithHotKeys.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:commandsWithHotKeys="clr-namespace:CommandsWithHotKeys"
        Title="MainWindow" Height="350" Width="525">
    <Window.DataContext>
        <commandsWithHotKeys:ViewModel/>
    </Window.DataContext>
    <Window.InputBindings>
        <KeyBinding Command="{Binding Command}" Key ="{Binding Command.Gesture.Key}" Modifiers="{Binding Command.Gesture.Modifiers}"></KeyBinding>
    </Window.InputBindings>
    <Grid>
        <Menu HorizontalAlignment="Stretch" VerticalAlignment="Top" Height="Auto">
            <MenuItem Header="Test">
                <MenuItem InputGestureText="{Binding Command.GestureText}" Header="{Binding Command.Text}" Command="{Binding Command}">
                </MenuItem>
            </MenuItem>
        </Menu>
    </Grid>
</Window>

Sure, you should somehow load the gestures information from configuration and then init commands with the data.

The next step is keystokes like in VS: Ctrl+K,Ctrl+D, quick search gives this SO question.

Question 2

If I haven't misunderstood your question try this:

<Window.InputBindings>
    <KeyBinding Key="A" Modifiers="Control" Command="{Binding ClickCommand}"/>
</Window.InputBindings>
<Grid >
    <Button Content="ok" x:Name="button">
        <Button.ContextMenu>
        <local:CustomContextMenu>
            <MenuItem Header="Click"  Command="{Binding ClickCommand}"/>
        </local:CustomContextMenu>
            </Button.ContextMenu>
    </Button>
</Grid>

..with:

public class CustomContextMenu : ContextMenu
{
    public CustomContextMenu()
    {
        this.Opened += CustomContextMenu_Opened;
    }

    void CustomContextMenu_Opened(object sender, RoutedEventArgs e)
    {
        DependencyObject obj = this.PlacementTarget;
        while (true)
        {
            obj = LogicalTreeHelper.GetParent(obj);
            if (obj == null || obj.GetType() == typeof(Window) || obj.GetType() == typeof(MainWindow))
                break;
        }

        if (obj != null)
            SetInputGestureText(((Window)obj).InputBindings);
        //UnSubscribe once set
        this.Opened -= CustomContextMenu_Opened;
    }

    void SetInputGestureText(InputBindingCollection bindings)
    {
        foreach (var item in this.Items)
        {
            var menuItem = item as MenuItem;
            if (menuItem != null)
            {
                for (int i = 0; i < bindings.Count; i++)
                {
                    var keyBinding = bindings[i] as KeyBinding;
                    //find one whose Command is same as that of menuItem
                    if (keyBinding!=null && keyBinding.Command == menuItem.Command)//ToDo : Apply check for None Modifier
                        menuItem.InputGestureText = keyBinding.Modifiers.ToString() + " + " + keyBinding.Key.ToString();
                }
            }
        }
    }
}

I hope this will give you an idea.

Question 3

This is how it did it:

In the loaded-event of my window I match the Command bindings of the menu items with the Command bindings of all InputBindings, much like ethicallogics's answer, but for a menu bar and it actually compares the Command bindings and not just the value, because that didn't work for me. this code also recurses into submenus.

    private void MainWindow_OnLoaded(object sender, RoutedEventArgs e)
    {
        // add InputGestures to menu items
        SetInputGestureTextsRecursive(MenuBar.Items, InputBindings);
    }

    private void SetInputGestureTextsRecursive(ItemCollection items, InputBindingCollection inputBindings)
    {
        foreach (var item in items)
        {
            var menuItem = item as MenuItem;
            if (menuItem != null)
            {
                if (menuItem.Command != null)
                {
                    // try to find an InputBinding with the same command and take the Gesture from there
                    foreach (KeyBinding keyBinding in inputBindings.OfType<KeyBinding>())
                    {
                        // we cant just do keyBinding.Command == menuItem.Command here, because the Command Property getter creates a new RelayCommand every time
                        // so we compare the bindings from XAML if they have the same target
                        if (CheckCommandPropertyBindingEquality(keyBinding, menuItem))
                        {
                            // let a new Keygesture create the String
                            menuItem.InputGestureText = new KeyGesture(keyBinding.Key, keyBinding.Modifiers).GetDisplayStringForCulture(CultureInfo.CurrentCulture);
                        }
                    }
                }

                // recurse into submenus
                if (menuItem.Items != null)
                    SetInputGestureTextsRecursive(menuItem.Items, inputBindings);
            }
        }
    }

    private static bool CheckCommandPropertyBindingEquality(KeyBinding keyBinding, MenuItem menuItem)
    {
        // get the binding for 'Command' property
        var keyBindingCommandBinding = BindingOperations.GetBindingExpression(keyBinding, InputBinding.CommandProperty);
        var menuItemCommandBinding = BindingOperations.GetBindingExpression(menuItem, MenuItem.CommandProperty);

        if (keyBindingCommandBinding == null || menuItemCommandBinding == null)
            return false;

        // commands are the same if they're defined in the same class and have the same name
        return keyBindingCommandBinding.ResolvedSource == menuItemCommandBinding.ResolvedSource
            && keyBindingCommandBinding.ResolvedSourcePropertyName == menuItemCommandBinding.ResolvedSourcePropertyName;
    }

Do this one time in your Window's code-behind and every menu item has an InputGesture. Just the translation is missing

Question 4

Based on Pavel Voronin's answer, I created the following. Actually I just created two new UserControls which automatically set Gesture on the command and read it.

class HotMenuItem : MenuItem
{
    public HotMenuItem()
    {
        SetBinding(InputGestureTextProperty, new Binding("Command.GestureText")
        {
            Source = this
        });
    }
}

class HotKeyBinding : KeyBinding
{

    protected override void OnPropertyChanged(DependencyPropertyChangedEventArgs e)
    {
        base.OnPropertyChanged(e);
        if (e.Property.Name == "Command" || e.Property.Name == "Gesture")
        {
            if (Command is IHotkeyCommand hotkeyCommand)
                hotkeyCommand.Gesture = Gesture as KeyGesture;
        }
    }
}

The used interface

public interface IHotkeyCommand
{
    KeyGesture Gesture { get; set; }
}

The Command is pretty much the same, it just implements INotifyPropertyChanged.

So the usage gets a bit cleaner in my opinion:

<Window.InputBindings>
    <viewModels:HotKeyBinding Command="{Binding ExitCommand}" Gesture="Alt+F4" />
</Window.InputBindings>

<Menu>
    <MenuItem Header="File" >
        <viewModels:HotMenuItem Header="Exit"  Command="{Binding ExitCommand}" />
    </MenuItem>
</Menu>