Like I mentioned in comment, control should have keyboard focus so that keyBindings can work on that control.
On button click it's working since with that click, userControl has got focus and hence bindings worked after that.
On UserControl load, put keyboard focus on UserControl so that input bindings can work. You can put this code in UserControl constructor:
public SampleUserControl()
{
InitializeComponent();
Focusable = true;
Loaded += (s, e) => Keyboard.Focus(this);
}
Also that can be achieved via XAML too (key thing is to set Focusable to True on UserControl):
<Window FocusManager.FocusedElement="{Binding ElementName=userControl}">
<local:SampleUserControl x:Name="userControl" Focusable="True"/>
</Window>