Easiest way is to use AcrobatPro (9 or X) If colours are tagged with one profile, then you can convert to another CMYK profile (not as good as device link though, but you probably have it at your disposal)
Use the colour converter to tag the objects you want to convert with an appropriate ICC profile (ISO Coated v2, FOGRA 27 or some profile that describes your assumed source). If you do not tag with ICC data CMYK will not be converted from one profile to another. (2 profiles with the same measure data, but different separation tables can used to repurpose.)
Now use the Convert colours again. This time check convert to output intent and choose a profile with a more reasonable TAC and GCR (After checking the kind of objects you want to convert, images, text, graphics, all) then you may also check off preserve black, (and if you like preserve pure colours).
An output in intent is a document wide colour profile, document data is "document CMYK" and if you disable colour management you will get the colours you see in separations in Acrobat. It will by default simulate your output intent. Preferably save as a PDFx-1a (flattened) or PDFx-4 (unflattened).