What heisenbert posted 11 months ago worked for me but I added one little extra thing.
Hard resetting iPhone.
Steps are:
Press Volume Up and let go.
Press Volume Down and let go.
Press and hold the side button, this will hard reset your phone. After your phone has turned back on, remove the watch app on your phone- re-install it. Factory reset your watch and pair. It worked for me.
Note: This does not wipe any data from your phone