If I understand you correctly you have more than 1 program: the http.pl server and one or more cgi scripts. PAR is not exactly made for that.

If you need to, you could convert all the programs to stand-alone binaries usin PAR, put them in a directory tree and create a zip of that, but at least your server.pl needs to be aware that the whole tree is likely in a different location than it is on your machine.

If you only have perl cgi scripts, you might be able to get the server.pl's perl interpreter to run the scripts, which means you only have to convert the server.pl and its modules with PAR and you can leave the rest unchanged.

CGI apps are easy for remote users to access, they usually aren't particulary easy to install :-)