Not surprising, since Math::Prime::Util's randperm is implemented in C

I think it's more about the fact that mpu creates $K scalars, while the other two creates at least $N.

That's why the performance of shuf approaches that of mpu as $K approaches $N.