Any wheelbuilding shop *can* do it, though it's possible that bicycle shops won't for whatever reason.
If you don't mind some days spent learning the skill, you can build it yourself; there's lots of wheelbuilding threads here, and tutorials and videos elsewhere, and a good reference book by Jobst Brandt "The Bicycle Wheel". Also a good basic bicycle mainenance and info site by Sheldon Brown.
To put the new motor in, first it has to have the right axle width for your frame--the same as the old one should be good.
If the spoke flange width and diameter is exactly the same between the two motors, you can probably re-use the spokes that it's built with now, but that's not very likely (and they're probably terrible spokes anyway, and likely too large / thick for the rim's design, a common mistake by ebike manufacturers; they often use 12g spokes in the mistaken belief that thicker is always better, without allowing for the rim's design limits).
There are spoke calculators like those at ebikes.ca that show you how to make the necessary measurements to figure out spoke length required on each side of the wheel (they're often different).
I'd recommend buying the Sapim 14/15 butted spokes, as they should make the best wheel; there are several places around the web you can find those. If you want to just get spokes at ebikes.ca while you're there using the spoke calculator, you can get the Sapim Strong single butted 13-14g they carry, which are the next best thing. I used those to build the wheels on my heavy-cargo SB Cruiser trike that I'm still using after several years.
