Right Shimano SPD pedal clicks on down stroke
It's a case of systematically hunting down the source of the click. As Andrew Henle said in a comment it's very hard to understand where a noise is coming from when you are riding on the bike. Once I was convinced I had a click in my bottom bracket but it turned out to be a slightly loose seat clamp.

Try wearing normal shoes and pedal on the SPDs (awkward, but can be done). That will determine if it's the pedal/cleat interface.

If it's still there check for play or roughness in the pedal bearings. Take the SPDs out and re-install your old pedals. 

If it's still there then you need to start looking at the BB or drivetrain.