All the channels are too damaged for any kind of "rescue" of those areas. It'll just be painstaking cloning, and/or swapping in areas of detail from another shot.
You don't need new prints. Of course your lab don't change they way they print just because one of their customers got a new calibrator.
Please check the prints you already have.
Thanks for posting. This is a very dangerous area.
Please read this: https://www.damiensymonds.net/2011/05/please-be-wary-of-cmyk.html
You MUST find out the correct profile to use.