Just a short thought on using 'our' and 'use vars' everywhere... You could also do what use strict wants you to do: Fully qualify all the variables you use.
There's quite a difference between a true global variable (as defined with use vars or our or my at file scope), and something like $Package::variable (which is also global in the sense that it's accessible from outside of the package that defined it).
First and foremost, you'll keep fully qualified variables out of the namespace (read "way") of other modules/packages/namespaces.
BTW, has someone mentioned file scoped lexicals? That's my-definitions at the file level, outside of all subroutines, or BEGIN/END blocks. These are global to anything within the physical file they're defined in. Are they in any way more/less effective than globals? Gut knowledge anyone? If your scipt is monolithic (in one file) you could use those, too.
Most of your local variables will acually be lexically scoped variables (my-variables). If there are some spots in your code where the behavior of local is really needed, it's still fine to use a fully qualified variable.
Since your script was meant to support perl4, too, it's acutally quite likely that merely substituting local with my will break your code -- however, I'd still give it a quick shot to get some orientation how much of a problem you really have. I could also imagine writing a short script that analyzes the your code to help you determine where work is needed (isn't there some perl4_to_perl5 converter out there?).
For example, if there are any local variables that are solely used within one block, and never mentioned outside that block, you can safely make them my vars. If however, a variable is used in the caller of a function, AFTER the function returned (mind loops!) you probably can't just go ahead and define it as a my variable.
Also, you should check whether using local everywhere (in subroutines) was just a habit of the author of your script, or if it's been used in a determined way. If it was a habit, substituting with my will be less of a problem I'd assume.
It all depends on the size of your project, but in any way, you seem to have some work to do... ;)