Juri,
I thought quite some bit on how we can add in a warning for key binding change. But as Stefan says, it is probably not worth it.
First of, we would need to create a wrapper function or a wrapper macro to create wrapper functions for all the commands that we want to phase out from being bound with the "C-x w" prefix map. The wrapper function will call the wrapped function and then issue a warning/message in the echo area saying that that function is already bound to "M-s h" prefix and will no longer be bound to "C-x w" prefix in future. After that, in a future emacs version, the final step to unbind those "C-x w" bindings will remain.