I run much older versions of AutoCAD than you probably do. I don't know if newer versions imbed real fonts, as opposed to the vector-drawn equivalents of old AutoCAD drawings.

I have Acrobat 7, and can import AutoCAD drawing files directly into the converter. When you are selecting a file from the box, there is a button marked "settings." This brings up a box showing PDF settings and security settings. You probably already know about this since you mentioned changing the preference. If you hit the button to "edit" these settings, one of the choices that comes up is "color," and you can choose to convert to CMYK.

A printer looking for Acrobat files is a new one on me. My printer wants PostScript, also in CMYK. I throw my photos into Photoshop, and my line work and AutoCAD into Illustrator to create these files. Illustrator is a good place to mess with AutoCAD, since you can play with colors and lineweights.