I know this isn't a very scientific method, but still :-) I'd import the color map to inkscape or GIMP and use the gamut warning to "mask" out of gamut colors. then capture the "masked" palette, then re-create the palette using the captured values. CMYK-Safe colors depend on the output CMYK profile, so it's probably impossible to have a generic "safe" palette without using a specific profile as starting point.

I'm pretty sure this isn't the best way to do it (there has to be a programatic way to do it using RGB and CMYK profiles to compile a palette, but I don't know how to do it).

IIrc the program Swatchbooker allows to choose profiles to "convert" palettes, but I could never make it work.

hth, Gez