Reset Activity Calibration on Apple Watch
Unpairing and re-pairing your WATCH used to reset your calibration data. However, as of watchOS 2.x, this is no longer the case, as that data now gets backed up to your iPhone.

It seems you are left with three options:


Take your WATCH on a few walks with the Workout app, hoping it eventually recalibrates itself.
Reset your WATCH as new by going into the Settings app on your WATCH.
Unpair your WATCH and perform an unencrypted backup of your iPhone to iTunes. Then restore your iPhone from backup, and pair your WATCH once again. You will lose all health data, passwords, etc. from your iPhone as well.


Seems #2 would be the most straightforward approach, although you could try #1 for a while and see if that’s enough.

I added #3 for completeness’s sake only