UPDATE to this post: https://discussions.apple.com/thread/250998383?answerId=252785388022#252785388022
Retried the update on my wife's phone again this morning. Went to check for an update: "Not connected to the internet". Tried again and got the Watch OS update screen for version 6-something. It had been telling us it was up-to-date at 5.3.7. Took 2 or 3 hours to complete the process, but watch is functioning again.
The only thing we did different is bring the watch and phone downstairs closer to the WiFi. That did not help trying to pair it to my phone -- all those failures were done downstairs, so it seems unlikely. I think a more likely suspect is glitchy Apple servers. We didn't really change anything else, so all I can suggest is to keep trying.