I had the same error message trying to reset and re-pair an Apple Watch series 3, to an iPhone 12. Short answer: if your iPhone is low on power, plug it in. Longer answer: It was being given to someone else, and we just wanted to pair it. The watch itself had not been updated to the new watchOS for a while. I also knew it my phone was on wi-fi. I was helped by another user here who had to switch to 'low battery' mode. That made me think ; my iPhone 12 was running low on power, so much that the indicator was RED. I just plugged in the iPhone to power, and then hit 'retry again' twice, and it proceeded. So make sure your iPhone has plenty of power, or plug it in. That worked for me.