You should only need to replace the sprocket, nothing else. If you put on a smaller sprocket to get higher gearing/slower pedalling you need a smaller sprocket, not a larger one. You may need to remove a chain link.
Those parts should be standard, the same as on an adult bike, and any bike shop should be able to make the switch. Coaster brakes are common in Europe on adult commuter bikes and in the US on "beach cruiser" type bikes.
You're looking at a cog like this:
Which is about $7 on Amazon, so probably $10 or so from a bike shop, plus labour. You could swap it yourself if you're a little confident - just take the wheel off, use a screwdriver to pop the lock ring, swap the cog and put the lockring back (beware: the lockring is a spring and likely to go flying). With an o-ring plier they're easy enough to reinstall or you can use a couple of screwdrivers to push it on. The only hiccup might be if you need to remove a chain link to get it to work, in which case you will need a chain tool as well.
The main issue is 15-20 minutes of the mechanics time, which will cost you. It will be cheaper if you pop the wheel off before taking it in, or at least make sure it's easy to do so (but if that's tricky you probably want the mechanic to do it all anyway).