More of an aside than a response to this question:

There appear to be several hundred "free CMYK converters" on the web, but very little about the quality of output for any of them except the glowing reports by the writers. This doesn't mean that many of them won't do a good job, but it would be up to you (and your printer) to proof carefully before the final printing to make sure you got lucky and got a good converter.

If there's the possibility of doing more of what you're doing now, it might be helpful to check out the Review of Paint Shop Pro Photo X2.

That review makes the statement:

Import and Export of CMYK Images
This is one of the most often overlooked features in affordable image editors … the ability to work with four-color printers. Most professional printers for book and magazine publishers still require images to be submitted in the Cyan, Magenta, Yellow, and Key/Black color format (CMYK). Corel's X2 is the only sub-$100 image editor we know of that provides the option of importing or exporting CMYK images.

Note that the review is about 3 years old and things sometimes change suddenly in the desktop publishing world, so there might be another image editing program that's added the capability now. The price for the program reviewed may also have changed some or it may be a different version by now.

For a look at the programs that professionals would likely use:

Converting to CMYK gives a "survey" of programs capable of publishing quality conversion, listed with separate instructions on where to find the conversion in each.

All of the programs suggested are in the range of $400 to $900 each, or were the last time I looked. For the most part, all these programs have rather steep learning curves and are not generally to be recommended for people not making a career in publishing.

A common way of getting the consistent results expected from the high-horsepower programs is to find someone who owns one and hire them to "finish" your creation so that it meets the specification of your printer. If you can find an appropriate person, the cost may be fairly nominal, although it is an extra cost. Several of the "significant" publishers pulled their document prep work "in-house" a few years back, so there likely are lots of "former job-shoppers" around who still have the programs and some experience, if you can find one.

*****
More specifically on the subject at hand:

The description of requirements your printer is asking for are typical for book publishing houses, and an "out" sometimes used by such print houses is to accept the input as "print files." Some print houses a while back insisted on this method.

This method lets you do it all, and relieves the printer of all responsibility for what the finished product looks like; but the method is simple.

You install a new printer on your computer. You don't have to have the printer, but you'll need to get the driver for a "book publisher quality printer" acceptable to the print house you plan to use. You can download printer drivers, e.g. for something like the Linotronic 300 v47.1, from Adobe. That one is a 1200 dpi massive high speed printer used by a couple of book publishers we worked with ten or so years ago. Your print house may want a different one. Set the "printer" on your computer to always "print to file."

Anything you print (to file), from any program, using that "printer" on your computer will produce a file that you can send to the print house (after you verify that they'll accept it as input). The print that the print house produces will be a good print, but the product will be only as good as the program you print from. (The file will be very large compared to the file you print from.)

You will need to discuss the requirements for your job with the print house you intend to use. If they won't answer your questions, in terms you can understand, the suggestion would be that you go somewhere else to get the printing done.

John