|Just another Perl shrine|
More difficult than choosing your testing toolset, you will need to decide what your tests should do. It's too late for coding to a specified test set ( which I completely agree with adrianh about - it's like magic ). Your code already exists and is in use.
I would begin by reviewing and rewriting the documentation. That will set in mind what the user interface is supposed to be like, what the internal API is to do, and will clarify the design in your memory.
Write user-level tests. In those, verify that the high-level documented interface works as advertised. Test erroneous usage for sanity. Then set these tests aside without fixing errors or improving anything.
Now start devising unit test of each sub. Your documentation of internals should guide you in what each should do, what error conditions may arise, and what tolerance each shold have for those errors. Do tests of each, from the bottom up. Induce error conditions to check for correct handling. Don't forget to test global data, too.
If your documents don't tell you what to test about a feature, that's a sign of probable hot spot. Study that closely and find out what the details should be.
Don't be too eager to change your design, but do keep an eye open for when you must.