You could also reduce memory overhead (at the expense of more calls to rand) by doing your random keep/toss within the loop:

my $lines = 0;
my $selection;
foreach my $path (split /:/, $ENV{'PATH'}) {
    opendir(PATH, $path);
    while (defined($_ = readdir(PATH))) {
        if (-f "$path/$_") {
            ++$lines;
            $selection = $_ if int(rand($lines)) == 0;
        }
    }
    closedir(PATH)
}
exec(man => $selection);
[download]