I did try resetting phone and erasing all content on apple watch - did not work. I also tried signing out of iCloud and signing back in - did not work. I tried forgetting internet, reset router - did not work. I went into settings and changed my region from United States (where I live) to somewhere else (Canada) - tried to pair and it worked!