Reboot aka power down/power up your S4 after the first time you pair each device.
My experience with connecting/pairing BT devices with my S4 is that after you pair a device, for the first time, you need to reboot the S4. I have 3 BT devices, Logitec UME Boombox, Lg Note/700 BT earbuds, Ford Sync.
I was able to connect and pair the to the Logitec UME Boombox. When I tried to connect and pair the Lg Note/700 BT earbuds, the S$ could not even 'see' the earbuds. After a reboot, the S4 connected and paired immediately. Again, when I tried to connect/pair to the Ford Sync, the S4 did not see it. A reboot, and after entering the Sync pin, it connected. I rebooted the S4 after connecting/pairing to the Ford Sync.
The S4, now connects and pairs to each of these devices as expected.
Good Luck,
Bob