This is becoming a bigger problem every day especially with 1st generation watcheds,ios13 doesn't seem to like watches with watchos5 or below,here is one proven solution from another forum;
Quote;
I found a friend, who was on iOS 12 and used his iPhone to pair. Before pairing it asked to upgrade the watch OS (iOS 13 didn't offer this option). After I upgraded the watchos I unpaired the watch from the ios12 phone and then was able to pair it with any iPhone running iOS 13.
I tried this myself with an old watch and phone that I have and can confirm that it works 100%.