PAR braucht folgendes um zu laufen:
http://par.perl.org/wiki/Requirements

Unter Windows installiere ich immer:
PAR
PAR::Packer


Bei Debian nutze ich es gerade nicht, aber du hast vielleicht gesehen, dass es auch ein fertiges Package für lenny (oder welche Distri hast du?) gibt?
http://packages.debian.org/de/lenny/libpar-perl

Vielleicht hilft dir das weiter.


//EDIT: renee hat Recht.
Cava ist auch eine schöne Sache unter Windows. Einfach zu bedienen. Hatte ich auch schon genutzt.