I also had the problem, that my Apple Watch did not pair, after replacing the screen.
But it was very strange, since the watch did pair at first. Then I was not able to add my credit card via Apple Pay or update to wOS 5.2.1 (from 5.2) and so I unpaired the watch, hoping that it would work once pairing it again.
Unfortunately it would not pair again at all.
So I opened it after reading this thread and figured out, that the GPS modules connector was loose and just fell of the display, when I touched the cable.
So connecting the (not working) display from another watch made it pair and upgrade again but still I am not able to add Apple Pay. I guess that it recognises the GPS module and since it is wOS 5 it works even though it is not the original GPS module. But I think, because it is not properly connected to all three cables of the display the GPS maybe is not able to fix a location which disables the Apple Pay function out of security or licensing reasons.