String::Approx is good as someone else said. So is Text::Levenshtein. With the values you can get from both modules, you should be able to do some math to get a percentage.

You might also want to read Levenshtein distance: calculating similarity of strings.