You can hit Esc before the combination to fill in for M and then it is just C-S-5 for me, which is certainly doable?
In some (most, I thought, but maybe I'm wrong) terminals, you can only use the control key to generate an actual control character -- i.e. one of ASCII 0-31. The ctrl key basically unsets bit 64 from the typed key, so ctrl-A through ctrl-Z generate ASCII 1-26, ctrl-@ generates ASCII 0 (though traditionally ctrl-spc gives this as well), and ctrl with [ \ ] ^ _ generate the remaining ASCII 27-31. Ctrl-? sometimes generates ASCII 127 (pretending that ctrl actually subtracts 64 instead of unsetting the bit), but otherwise there are no remaining ASCII values left for such extensions as ctrl-%.
"C-M-%" is pretty much impossible in the terminal. You have to do "M-x query-replace-regexp", or make some other custom binding.