Like most people here, it took me awhile to finally get this working. I tried several of the combinations mentioned repeatedly. I was trying to pair a series 4 watch with 11 iPhone pro. These are the steps that finally worked for me:
reset Watch to factory settings
uninstalled Watch app on iPhone
updated my iPhone
turned iPhone off/on
reinstalled Watch app
turned off cellular on Iphone
proceeded with pairing like normal
both my IPhone and my watch were hooked up to chargers when I attempted to pair them
Not sure if all of that was necessary but it was the winning combination. Hope it helps.