FYI: Step 1 of the above is not necessary anymore for PAR::Packer 1.006 and above (the changes have been incorporated).

Ad step 2: What you really need is that your PATH must include the directory where the actual C compiler (cl.exe IIRC) lives (Visual Studio's, but the same advice holds when using MingW as well). If you then run the CPAN shell with this PATH, it will correctly detect your installed C compiler and the will try to use that when build PAR::Packer. Also, nmake (or dmake) must be found in your PATH.

Maybe the Visual Studio C compiler itself needs some additional environment settings, in old times (when I had access to Visual Whatever) there was a .bat script somewhere that set up PATH and all other variables.
Steps 3-8 are just the sequence of commands that the CPAN shell runs when you do "install PAR::Packer", except for the strange error in step 5 (that seems to magically disappear when repeated). If this error is still there, the CPAN shell will stop at this point. PAR::Packer 1.001 - 1.005 contained a bug that might have triggered this behaviour which is fixed in 1.006 (can't tell, because the actual error message isn't in the above post).
So my advice is: after you set up your PATH as described above, just try installing PAR::Packer >= 1.006 via the CPAN shell.
Oh, and another thing: Perl 5.10.0 breaks PAR::Packer. Any Perl version below or above is fine, but 5.10.0 breaks PAR::Packer's method to intercept the loading of "glue" DLLs. Your PAR::Packer may appear to work as long as you run your packed executables on the same machine where you generated them (or on a machine with the exact same Perl installation). The trouble starts when you run the packed executable on a machine that has no Perl installed or a different version of Perl than on the build machine.