This answer is not for Illustrator, but for 'some other tool', namely Ghostscript (download gs871w32.exe
or gs871w64.exe
).
Ghostscript allows you to 're-distill' PDFs (without an intermediate conversion to PostScript, the dreaded 'refrying' detour). Try this command:
gswin32c.exe ^
-o c:/path/to/output-cmyk.pdf ^
-sDEVICE=pdfwrite ^
-dUseCIEColor ^
-sProcessColorModel=DeviceCMYK ^
-sColorConversionStrategy=CMYK ^
-sColorConversionStrategyForImages=CMYK ^
input-rgb.pdf
And if you are able to wait for a few more weeks, Ghostscript 9.00 will be released. This new version will sport support of colormanagement (based on LCMS) with ICC profiles for the first time ever...
UPDATE: I updated above command because I missed to put in the option to also convert images.
Update 2
If color conversion does not work as desired and if you see a message like "Unable to convert color space to Gray, reverting strategy to LeaveColorUnchanged" then...
- your Ghostscript probably is a newer release from the 9.x version series, and
- your source PDF likely uses an embedded ICC color profile
In this case add -dOverrideICC
to the command line and see if it changes the result as desired.