The closest I have gotten is following the instructions in the first link -- the Catalyst Manual.
Did you heed this part:
(assuming the server is setup to handle .pl as fcgi - you may need to rename the script to myapp_fastcgi.fcgi and/or use a SetHandler directive).
I might be wrong, but just in case do check that your server does handle .pl as .fcgi, and not accidentally handling .pl as would be in a plain cgi-bin (or rename/symlink your scripts like so.) Otherwise, you probably need to escalate to your server provider to enable handling .pl as .fcgi for your virtualhost, among others.