Personally, I like to write multiple modules that all implement the same API, like the following:

package Super::Cool::Perl5_006;

# The most basic implementation
[download]

package Super::Cool::Perl5_008;
use Super::Cool::Perl5_006; # First import all the stuff from 5_006

# and overwrite some of the newer stuff
[download]

package Super::Cool::Perl5_010;
use Super::Cool::Perl5_008;

# Not totally basic implementation
[download]

The package Super::Cool then basically loads the appropriate implementation package and exports the subroutines into the calling package.

This approach is great until you have a longer subroutine which has a common setup case and then one (or more) special cases after the common setup. My approach would then move the special handling into a separate subroutine, which makes the code more disjointed as the logic is then spread out over more subroutines. The alternative would be to copy and rewrite the subroutine for each Perl version, which carries its own hazards.