I had the same issue after replacing the screen of a Series 2 (on WatchOS 5.1.3) : impossible to pair it with my iPhone 7 (iOS 13.3.1).
I have just found an alternate solution, using my old iPhone 6 (on iOS 12.4.5) : it didn’t ask to update the watch for pairing and succeeded to pair on my first try !
I then updated the watch manually, to watchOS 5.3.6, unpair it and pair it to my iPhone 7 successfully !
My theory : an old iOS version can pair a watch with an old watchOS and be used to update the watch.