Może banalne pytanie ale je zadam. Próbowałeś wyłączyć bluetooth w telefonie? Ewentualnie usuń słuchawki z urządzeń sparowanych w smartfonie. Dopiero wtedy wykonaj proces parowania z Gear S3.
Miałem podobnie tylko u mnie zamiast słuchawek Bluetooth problem był z modułem Bluetooth Samsunga, pod który podpina się słuchawki 3.5mm jack.
Sparowany wcześniej moduł z Gear S3 nie był widoczny później gdy chciałem go ponownie użyć z telefonem.
Tapnięte S-ósemką