This worked for me. Make sure youre connected to WiFi.
Manually pair Apple Watch
When iPhone prompts for an update to Apple Watch, go to settings (do not close apple watch app!)
Turn off bluetooth
Go back into Apple Watch app
The update should then proceed