What's the difference between the different "rename" commands?

Solution 1:

How come there are two packages providing different commands using the same name (if not by accident)?

That's not unusual. Authors typically pick the simplest command name they think of, so if two people write a command to rename files, it's likely they'll both name it rename. That's one of the reasons behind the Debian Alternatives system - it allows packages providing similarly-named commands to coexist, and for one package to replace another. For example, there are multiple AWK implementations - mawk, original-awk, gawk (though they all refer to themselves as awk). With the alternatives system, you can install them all at the same time, and conveniently switch between any of them as the default awk.

In this specific case, prename comes from the Perl source code. The Debian package maintainers originally had rename be the Perl one, then switched to the alternatives system, to accommodate the rename from util-linux. Then somebody wrote an improved version of Perl's rename in the File-Rename Perl module, which was then added as another alternative. But that's not even the only Perl module for renaming files.

Wouldn't it be rather straightforward for the perl package to either include the “full” rename command or not include any rename command at all? Why is this seemingly uncomplete split sustained until at least Ubuntu 17.04?

See Debian bug #735134 for how this situation evolved. Debian maintainers generally prefer going at least one release when doing something drastic, like replacing a working command with another. prename was kept around for jessie, and has now been removed for buster. In addition, it looks like rename will no longer be under the alternatives system, since rename.ul is too incompatible. rename will be just file-rename.

Since Ubuntu generally picks up packaging changes from Debian, what happens to rename in Debian will be picked up by Ubuntu sooner or later, probably in 18.04. It seems to be too late for 17.10.

What exactly are the differences between those commands?

Fundamentally, both prename and file-rename run Perl expressions to rename files. file-rename is just actively maintained and supports more options. rename from util-linux works entirely differently, has its own rules for patterns.