If you're going to be playing in Arena...

Your opposition will likely pick a single target to burn.
They may switch from one to another, but the damage will end up focused on whatever they want to kill.

The Paladin is good, because they wear plate, carry a shield and passively heal themselves (Protector of the Innocent) plus their Beacon target (often themselves), while putting out very impressive healing throughput on whatever is being focused down.
They also have an easy to macro (two macros alternating) healing of a focus target, which puts out a lot of healing... just change your focus to whatever they burn.
Plus some immunity effects, and the "big button" of several cooldowns available at once.





In a battleground environment, the healer will still likely be seen as the vulnerable point of the team.
Having survivability options is going to be a good thing.
Many will stupidly attack the target on them, while you heal your DPS... but some will have a brain and choose to use it.

In general, your opposition will be much less focused and coordinated, in assorted battlegrounds.

Every healer will be a decent choice.

Look at the strengths of the different choices and go with that.
A druid brings stealth to the table, and can use Symbiosis on one of the other Warlocks for whatever effect each gains.
The paladin has higher survival and strong single target healing.
The shaman has high survivability, and their totem buffs.
The priest has good aoe healing, and can Mass Dispel.

I don't think any healer is necessarily the wrong choice.
Each just has their own flavor and benefits.