Greetings.
Background: iWatch Series 1 38mm - had battery issues, sat for a long time. Fixed the battery, attempted to pair with an iPhone 12 mini iOS 15.latestpatches without any luck. Tried everything mentioned in this post (probably twice).
Solution: Luckily I had held on to an old iPhone 6Plus. Brought back to life (iOS 12.latest), perform reset on iWatch, install watch app, pair and upgrade software on iWatch, unpair it from old phone and pair it with new phone.
I hope this helps you.
Cheers.