I don't use Desktop icons, or Windows, but just as a learning exercise, lets see what it would take? First you would need to make a new icon on the Desktop, then you would have to assign it an image(or use the default one), then add a Caption Text, and the full path to the Perl Program to be executed. All these things can be done with right-mouse-clicks on most modern Desktops.

I think it could be done but it's not a Perl problem, it's a WindowManager issue. What you probably are looking for, is a generic program installer for the Window's WindowManager.