Indeed, it would be interesting to fuzz-test the Perl interpreter by (Markov-)generating Perl code and parsing that code. But as this will only uncover bugs and memory leaks in the compiler part of Perl, there is little to be gained, security wise. If you are in the position to evaluate arbitrary Perl code, fuzzing isn't necessary anymore.

Fuzz-testing (web) applications is a more promising avenue in my opinion, because there can well be oversights when handling input values in your program, even if you're running under taint mode. I've thought a bit about automating submission of generated form values and then hunting in the output for error messages or something that indicates that the application crashed or behaved unexpectedly. But as I didn't have a concrete application, and writing a general fuzzer was too complex, nothing came out of it. Writing the form submission is nearly trivial, but writing the evaluator that checks whether the result is as expected or deviates was what kept me from implementing something.