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-%.
No, you're right. As far as I know, standard vt100/ANSI terminals do not have any special escape sequences for control key combinations that don't map directly into ASCII.
"C-M-%" is pretty much impossible in the terminal. You have to do "M-x query-replace-regexp", or make some other custom binding.