I've yet to figure out if downgrading the bluetooth firmware on the HU would be an option. Every time I select Pandora as a source, my phone says "Pandora Accessory" and starts blaring music from my stupid little phone speaker.
It's pretty easy to install the BT firmware on the HU - without reverting everything back to 4.0. You just need the previous upgrade SD. Copy just the FIRMWARE directory to another SD. Then manually install the old firmware from Settings/Bluetooth.
Not sure if there will be other side-effects, but if so - just load the current one again.
Since I primarily use my old iPod for music, I haven't been annoyed enough to dig into this. But yes, things got much worse with Lollipop. Since you are running a custom ROM, I don't see why you couldn't find a KitKat based one. There should be several around still.
On my Nexus 5, I'm running the stock factory release - rooted. If it bothered me a lot I'd just load the KitKat 4.4.4. It's still on the google web-site. https://developers.google.com/android/nexus/images. I guess you have an S4, I don't know where you'll find images for that.