On a new stage3 file upgrading it seems that dev-perl/Locale-gettext is missing which is required to pass the configure tests for sys-apps/help2man.
It already has this dependency, you probably upgraded perl & did not yet do "perl-cleaner --all". A simple RE-build of Locale-gettext will work too.
Yes, I did a rebuild. I also saw that perl-cleaner was mentioned in the logs. Obviously it solved the problem, but it did break my emerge. Would it be "possible" to enforce perl-cleaner automatically?
In a way, yes. With some new features in EAPI 5, these kinds of problems should soon be a thing of the past: http://wiki.gentoo.org/wiki/Sub-slots_and_Slot-Operators#Making_perl-cleaner_obsolete
*** This bug has been marked as a duplicate of bug 149490 ***