I had the same issue with a watch I hadn't used for a while and needed to pair to my new phone. I followed the steps dogr suggested (restart phone and watch, low power mode on phone) and that worked for me.