I had this with my Nokia Lumia 800, could never get it to work, it would be paired but I would make a call and it would just operate the phone. I upgraded to a HTC One and that works fine.
The only thing you can try is deleting it and re-adding but I think there may be some phones that aren't compatible, would be surprised if the S4 is one though.
