Hello Rhaza,
Versatility and Haste are very close in PvP.
Basically Haste will always give you slightly more overall damage, whereas Versatility will grant you a bit more survivability and more healing.
I prefer Vers in most cases as I am the target against 90% of the teams that I face.
As for the staff go for the Wild Combatant's Battle Staff (Haste/Multi) along with the Haste enchant.
Hope this helps, gl!