I had a S4 for a while. I had issues with newer BT headsets connecting. I find with Android devices when they start to age, they are no longer are supported with apps and hardware. Do any of your other BT devices have issues connected to the S4?
If not, I would contact firstname.lastname@example.org and tell what steps you have done. They might have some better tips to get you connected or tell you if there is a compatibility issue.