Does "Stink Bomb" damage the Paladin when he is the first hero?
As @Samthere said, the word new is to clarify they are refering to the character that is in the first position after the first effect of the card.
Anyway, let's go to the rulebook, page 17, Paladins:


  The paladin is a special adventurer that is always at the front of 
  the party. Any new warrior will push ahead of everyone but 
  the paladin. 


So the card specifies the Paladin won't move so it does not go against this primary rule, but the Paladin will take the damage anyway.