As others have said, PAR is an excellent solution. If you have need to do this often, I've had excellent success with the commercial Perl "compiler" PerlApp, included with the ActiveState PDK. There's a cost, but it works very well and carries support from ActiveState if you ever have problems. If you're doing this for commercial distribution, especially, ActiveState is the way to go.

With either solution, you don't need to have Perl installed on the target machine, as it (and necessary modules) are packaged together inside the EXE. This carries the added advantage that your users can't break your programs by upgrading (or removing, etc.) their Perl modules.