From the sound of things, no punishment is needed.
He *did* make the promise too lightly, but that can be your hook to bring him back to the situation.
Every night, starting the night the girl is "Zombified", the Paladin has a dream. A dream in which he is standing in the woods, lush and leafy like the height of summer. Then the woods turn cold, the trees bare; and a little voice echoes "you PROMISED !" He runs through the woods, but only hears echoes of the voice "you PROMISED !". And he wakes in a cold sweat.
Quasqueton said:
A promise to a little girl to always protect her, when she is scared in a big dark forest is not the same thing as a holy vow to always protect the king.
Oh, but they are the same thing. The one to whom you made the promise is irrelevant. Likewise, whether the dangers were shadows among the trees or assassins among the servants, a blanket promise of protection is equally binding.
The only difference is whether the deity of the Paladin is involved. An oath "I swear by the god X" is slightly more binding than "I promise", but more because the Paladin in that case has dragged his/her god into it. Now there are 2 entities (the Paladin and his/her god) who "lose face" if the Paladin reneges on the promise. The god typically won't stand for that.
If the Paladin "only" promised, s/he still has made a commitment. The Paladin's powers are predicated on the Paladin being the sort of person who follows through with commitments.
The other question is, what did the Paladin promise ? If it was to keep the little girl safe always, then the Paladin made an unwise commitment. If it was to keep her safe until he could return the little girl home, then that is what was done, and there is no "foul" on that.