Is 10MB really that big these days? If that is the total size then I don't see the problem since none of your target environments seem to be resource limited. If it is 10MB per exe then size is something to be concerned about given the number of utilities (and a quick check indicates that's the case).
You also aren't restricted to 5.8. PerlPowerTools has passes for many recent perl versions across a range of OSes on CPAN Testers. http://matrix.cpantesters.org/?dist=PerlPowerTools+1.027
I guess a more general question is whether you need to use the perl variants of these tools given that they are likely to be available on the unix variants, and there are ways of getting them for windows through systems such as cygwin and msys2? Strawberry perl comes with at least some of these utilities under its c/bin dir, so you could distribute those as a start. If you can determine where they are sourced from then you can probably get more from there.