Hi everyone I was also having this issue because Apple had to replace my iphone X after damaging it in store fixing my camera…my series 3 watch was happily connected to my original phone but refused to connect to the replacement one and insisted on an update to the watch which said it would take 24hours (!!!) and then failed to update after all that anyway. I tried restarting both devices and resetting the watch, turning off Bluetooth, changing the location/language as suggested in this forum and none of it worked. I was then clicking through almost all options in settings to see if anything looked remotely relevant and went into the name/ID bit with my initials at the top of settings, scrolled down and it listed my devices of which one of them was my watch. Clicked into the watch and selected ‘remove from account’’. For whatever reason this then allowed me to pair with my watch without updating. I’m not sure if this will work for others but worth a try?