I just went through this after I got a new phone and had to pair to it. I ended up trying holding down BOTH buttons for several seconds and it went into pairing mode again and was discoverable. Maybe try that.
If you have a used Apple Watch, it may still be synced with another device. Go into the Settings menu on the watch and tap "Reset" to completely erase its...