Have you tried going into the Settings -> Bluetooth menu on the watch while attempting to pair? I went through a period where my Pebble Time Steel was losing connection & refusing to pair quite often, but it worked if I was on that screen. But I probably also had to try rebooting the phone & sometimes forgetting the pairing on the Pebble.
Ultimately, the bug was that my Nexus 5 phone was dying hard (failing battery & spontaneously rebooting). I’ve since bought a Galaxy S8 and it’s staying paired and much more stable.