I had the same issue and contacted Samsung support. After being on the phone with them for over 30 min, here is the solution that worked:
Go to your settings on your Gear 3. Choose About Gear 3. Reset.
After Gear 3 resets and reboots, your phone will pickup the Gear 3 in notifications via...