Cool. I can highly recommend Andy Lester's excellent module-starter script to build a skeleton structure for your module. You can then drop your existing code (which I've not downloaded) into that structure. Then just do perl Makefile.PL, make dist, and your module is ready to go.

I've also had good success with Perl::Tidy and Perl::Critic to clean up and standardize code. The latter works like a Perl version of lint, which I used for a couple of years when I did C development. It asks those difficult questions like "Are you sure you want to do this here?"

Finally, and you've already heard about this, tests are good, tests are great. They find the darndest things. Write lots of tests.