for %q in (*.cgi *.pl) do (
   perl -pi.bak -e"s{^#!/usr/bin/perl}{#!/usr/local/bin/perl}" "%q"
)
[download]

Change for to for /r for a recursive solution.

Update: Simplified solution