|Don't ask to ask, just ask|
Do they have any in-house Perl programmers? If not and they have programmers more conversant in the other language, I'm afraid your quest is doomed from the start.
Missing documentation can hardly be blamed on Perl. One can write missing documentation in any language.
Alas, the "complicated code" thing is something which will haunt Perl forever it seems. Telling them that it could have been written in a more understandable way is not going to help you.
Could you not offer them to re-write these scripts into more "Perl Best Practices" compliant Perl? And add some tests too, so they have a fine base to upgrade their scripts if necessary? If they have to pay another programmer to re-write these scripts in another language, it will cost them a fair sum too and you already have obtained a good working knowledge of these scripts by documenting them. It seems to me you can thus undercut any other programmer who has to start froms scratch, unless you are very expensive of course! ;-)
I had a similar issue last year in my company when the head of IT found out all my scripts are written in Perl (of which he understands nothing it seems) and wanted it to be re-done in another language (he was thinking of PHP, but only a small part of my scripts are web-server based). I then told him that he was going to exchange a perfectly working mission critical system for something which did not yet exist, which had to respond to a constantly changing environment at the drop of a hat and his already overworked IT department would never be able to do so in any reasonable period of time. He finally agreed with only the web-based parts to be switched to PHP as indeed Perl was far superior in the other tasks. The lesson from this story: argue from Perl's strengths (text processing & parsing) and don't pick a fight you cannot win.
A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James