It depends which version of the Khamsin you have.
Some have a steel axle and no adjusting collars, these were discontinued in model year 2013 and later ones have adjusting collars and alloy axles.
Either way, if you have play which can't be taken up by the adjusters (if present) then new bearings for sure.
Our advice is - and I am ready to be slagged off here as having an interest in saying this - which is fine, I'm used to it & it doesn't change the truth of what I say - Campagnolo bearings rather than generic bearings are the safest bet. Generic bearings are generally made (with varying degrees of accuracy) to the ISO bearing dimension standards whereas Campagnolo specify their own dimenional tolerances to their bearing suppliers - we have seen generics that were a very loose fit in the hub recesses, as well as some that were so tight that with the axles fitted, they turned in "steps" - all cartridge bearings are not created equal.
Other things to be careful of - lateral play aside, in some cases, roughness in the rear bearings is not the hub bearings at all, it can be the cassette body bearings - they are two totally separate systems, the wheel bearings are load bearing and the cassette body bearings are not (unlike in a genuine Shimano hub - Shiamano clones do it all sorts of strange ways). Cassette body bearings can be changed but in older cassette bodies it's tricky as the inner bearing is retained by a c-clip (not a circlip) that needs to be removed to get the bearing out - and it's not easy without the right tools & technique.
Make sure the shop has the right presses to do the job - yes, I know you *can* use a drift and a hammer, or two old bearings on top of the new ones - but in general it's a lot harder to get the bearings in dead square (which they need to be) and if they tilt badly off line during fitting they can end up messing up the bearing locations so you'll never get them in dead right again (seen that far too often) ... better that they are squeezed in with a press and the correct collars.