I believe that you need to either include the DLL or have Perl installed on the machine. That's based on the following excerpt from the Perl Dev Kit User Guide:

    The PerlApp utility converts a Perl program into an executable file. The executable can be freestanding (for use on systems where Perl is not installed), or dependent (for use on systems where Perl is installed). Freestanding programs built with PerlApp are larger in size than dependent applications because required Perl modules are included in the executable.

The only other alternative would be to copy the perl58.dll to the other machine. I believe that ActiveState's licensing does allow for that, especially since PerlApp is essentially bundling it into the stand-alone executables.