While that is a valid suggestion, I would go one step further and suggest you use CPAN.pm to install PAR. If no C compiler is availlable, the PAR installer will download a PAR binary for your platform.
Of course, the binaries from CPAN aren't better than the ones from uwinnipeg per se. They just have the distinct advantage that I built them and so I can be of more help in debugging.
The best advice, however, comes from the PAR homepage itself. Just use the binary that is confirmed to work on your system as identified by http://par.wikia.com/wiki/PAR_PPM_Compatibility_List
Hope this helps,