Hello nysus,
I have encountered the same problem when creating services with the macOS Automator application. In Automator, one can create a
workflow, and then place a
run shell script step inside the workflow. An entry of
/usr/bin/perl appears amongst the shell choices, but I don't see a way to choose a custom path. It seems that Automator uses the system perl, so I've always kept my Automator perl scripts very simple such that the system perl will work. Using an AppleScript (or other type of script) to launch the perl script might provide a work around. Hopefully someone will have a good answer to your question, and I will look into this more myself.
Also, I noticed that you cross posted your question here. It's considered polite to mention cross-posts in order to minimize duplication of effort.
UPDATE: Try to use absolute paths in your AppleScript like this:
do shell script "/Users/stevied/perl5/perlbrew/perls/perl-5.22.2/bin/p
+erl /Users/stevied/bin/clean_desktop.pl"
This seemed to work for me in Automator. Of course, you may need to change
perl-5.22.2 to the version of perl that you have installed.