Create a folder before starting your action that was recorded and name it 'CMYK images' or whatever you want.
Go to the automate->Batch and run the action you prepared. Choose your source folder, and then choose a new destination folder and there is a checkbox for overriding the save in your action (or you can delete it).
When the batch is done, you'll have a second copy of your images (yet they will have the same names as the originals). You can rename them using a finder-system renaming utility, or manually if you need to do so.
So you can move the resulting files into a new folder, but renaming isn't possible with the actions unless you interrupt and save them manually. I've gotten around this by using a different format and making sure it has a different automatically appended extension (JPG) or (EPS) from the originals. Its not really that difficult to do renaming.
Finder renaming can be done with a few apps on versiontracker. Search for "rename file" at
www.versiontracker.com in the MacOS9 section. There's a bunch you can download from there.