Make sure your headphones is not connected to your phone or computer or anything else. Turn off bluetooth on those devices to make sure they will not connect to the headphones. Then start searching for headphones on the watch. After that you turn on the headphones and put them in pairing mode.
After you've paired them the first time my tip is to always start search for the headphones on the watch first and after that turn on the headphones to prevent them from being connected to the phone or computer. Sometimes the phone will still connect to the headphones. Then you need to turn off the headphones and do it again.
Good advice for 'phones that are paired with other devices.
In my case they're dedicated 'running' headphones and if I don't switch them on before firing up music/playrun on the watch they'll fail to connect and I'll need to restart the watch to get back to a good state!
