[Plugin: Permalink Converter] Doesn’t WordPress do this already?

Yes, WP will redirect the user to the permalink.

I looked at the code for that plugin – basically it is for people who have non-permalinks scattered around their old posts/pages, but are now using permalinks, and want the old links to look nice.

Even though it will still take visitors to the same place, it just makes them look nicer, and it is easier than going through the old posts manually to change them.