Bomb warrior is slightly better if you can manage to establish a good board. But you will probably still lose, because reborn paladin has massive heals as well
What massive heals, he runs 3 healing cards ussualy, And possibly only copying zilleax for heals. Of you win early board, warriors removal does not need to trade minnions and ussualy wouldnt struggle to remove minnions with spells only not allowing heals.
Though problem with warrior with bomb package is different. Paladin might draw bombs too late or never draw them at all if he gets board advantage and just ends game early.