Can you try factory resetting the watch? Remove the watch as well from your phone, then make sure the watch is also no longer shown on the Pixel Watch app. Try clearing cache and storage of the Pixel Watch app as well.
After that, set up the watch again, and see if you can connect the watch to your phone. Please report back the result.