Any phones that support multiple concurrent bluetooth devices?
Yes, most devices support up to 7 devices connected at once. I don't have a Galaxy S4 to test on, but it seems unlikely it would only support one. More likely, there's a particular problem with one of the devices involved.

You should post a new question about why Bluetooth isn't working properly for you, giving full details of the devices you're using, what steps you take, and what happens.