I have had a similar problem.
Followed all proposals (delete from phone, unpair on watch, restart phone, etc.)
Watch is found - all good - until the watch returns to the time screen. Connection is automatically lost and the phone and watch have to be reset and paired again. Most annoying!
Any suggestions please.