Unless you have some objects with WHITE outlines (as distinct from no outlines at all) and assuming you haven't used "Registration Colour" as part of your design) you should be able to do it like this:
1) Edit : Find and Replace : Replace Objects
2) Replace a colour model or palette
Find any colour model or palette
Replace with the colour model: Registration Colour
Replace colours used as outlines
Finish
Replace All, OK, Close
3) Repeat 1
4) Replace a colour model or palette
Find a colour model: Registration Colour
Replace with the colour model: CMYK
Replace colours used as outlines
Finish
Replace All, OK, Close
This will leave all outlines set CMYK:100,100,100,100 which is probably not good if you are litho printing (too much ink density) so you probably want to go in to the wizard again, this time selecting "Replace a colour", choosing CMYK:100,100,100,100 as the old colour and something like 50:0:0:100 as the new colour.
This still leaves us with the problem that if you had any WHITE outlines (as opposed to NONE) they will also become black. But you can probably solve that too. BEFORE you do any of the above.
a) Create a new layer
b) Edit : Find and Replace : Find
c) Construct a find that picks objects with WHITE outlines
d) Move all selected objects to the new layer and set that layer NON-EDITABLE.
Now perform steps 1-4 and it will skip the objects with white backgrounds.