++ Much improved. My point with mentioning "quotes" was I was hoping When C<all> or C<undef> is selected would be When C<'all'> or C<undef> is selected (and similarly for other textual literals, like C<'by keys'> or C<'keys'>). But with the examples that now follow, that's quickly clarified, so it's not critical.

nitpick #1: random_from_list should be included in @EXPORT_OK

nitpick #2: in the =head4 keys section, there are typos of "randon" and "randon_color"

I agree with hippo that List::Random and Random::List both seem to apply as reasonable names. Given Random::Set and Random::Day, which both select a random element from a group, I think I'd have a slight preference for Random::List, because your module complements those nicely. (I agree with your OP, in that taking the top spot of package Random; is not appropriate.) I also ++agree with hippo's Synopsis suggestion.

Don't worry about long POD: in my opinion, long-but-helpful is much better than short-and-unhelpful. As a new user to a module, I want it descriptive enough that someone who doesn't have the author's history with the module would be able to read the documentation and immediately grasp what the module is about and how to use it.