Something looks strange with your @INC. Compare with mine when I make it fail on a nonexistent package Zowie:
C:\Kai\perl\PAR test>pp -o test.exe test.pl
C:\Kai\perl\PAR test>test
Can't locate Zowie.pm in @INC (@INC contains: CODE(0xd9d784) C:\DOCUME
+~1\KAICAR~1\LOCALS~1\Temp\par-Kai_Carver\cache-1105735837/inc/lib C:\
+DOCUME~1\KAICAR~1\LOCALS~1\Temp\par-Kai_Carver\cache-1105735837/inc C
+ODE(0xd306d8) .) at script/test.pl line 3.
BEGIN failed--compilation aborted at script/test.pl line 3.
C:\Kai\perl\PAR test>
The part with the cache where everything is supposed to be stored is missing from your error output.
Also, can you maybe try to install PAR using ppm, rather than CPAN.pm?
http://www.nntp.perl.org/group/perl.par/1705
ppm install http://www.bribes.org/perl/ppm/PAR.ppd