CMYK and PMS are almost always different to some degree. I recommend picking them at the same time. Use a Pantone colour bridge that shows both CMYK and PMS, and from there try to pick colours that match each other well. That way you will give you an impression about how the colour looks in print.
You can always print tests of different CMYK variations and maybe find something that matches better than the colour bridge one, but chances are that it will be time consuming. And as soon as the paper or the print house changes, it can look totally different.
I would also recommend informing the clients about variables that affects colour, such as colur space, printing techniques, paper, lighting etc. Show them some relevant examples. That will hopefully lead to realistic expectations, because colours will look different.