Hi, I had exact the same problem a I solved it. Here is how:
1, first connect your samsung gear s3 using bluetooth to the phone and after that
2, Open Samsung gear application a begin pairing process (it requieres you to install two more samsung services - install them)
3, install samsung health and it should work.
4, again if you will have any problem with connection connect the watch manually via bluetooth menu in your phone.