After you have factory reset. Try this which I had to do in order to even get it set up at all on my Samsung Note 8. This comes from Fossil Support:
Make sure Bluetooth is turned on needless to say.
Location services been turned on as well.
Your phone should have good network connection, strong and stable WiFi connection is recommended.
Go to phone settings and choose Apps/Application Manager, find the Android Wear app and click into it. Choose the option for Storage and choose "Clear Cache"
Go back one time and choose the permissions, make sure the location option is enabled
Go back to the app settings, now click on "Force Stop"
After we fully close the app, please try to reboot your phone then open up the app. Choose the option to Pair With A New Device, the app will ask you "Have a watch, set it up"
After I did this, it resolved, after clearing cache, forgetting and re-paring. Took about 45 mins after it paired to complete. Good Luck