how to hide a button that is bound to a command that cannot execute?

You could use a Style and Triggers, assuming that the command is in charge of setting the Button enabled/disabled:

        <Button x:Name="btnMoveUp"
                Command="{x:Static local:Window1.MoveItemUp}">
            <Button.Style>
                <Style TargetType="{x:Type Button}" >
                    <Style.Triggers>
                        <Trigger Property="IsEnabled" Value="False">
                            <Setter Property="Visibility" Value="Collapsed" />
                        </Trigger>
                    </Style.Triggers>
                </Style>
            </Button.Style>
        </Button>

Note that you can define this Style at a higher scope and share it – I just put it right with the Button for a more compressed example.