Vou adivinhar e postular que seus arquivos (desenvolvidos no Windows) estão no formato DOS (CRLF).
Isso irá interferir com o shebang, falhando com mensagens não tão claras:
$ ./my_script.pl
: No such file or directory
Veja o link sobre como verificar suas terminações de linha.
Por exemplo:
bash-4.1$ cat -v my_script.pl
#!/usr/bin/env perl^M
^M
print "Hello World\n";^M
^M
Depois, há ferramentas diferentes (por exemplo, dos2unix ou fromdos) que ajudarão você a converter seus arquivos de texto em finalização de linha Unix adequada.
Após a conversão:
$ cat -v my_script.pl
#!/usr/bin/env perl
print "Hello World\n";
E você poderá executá-los:
$ chmod 755 my_script.pl
$ ./my_script.pl
Hello World