Letting a point free is a very good idea to try understanding how the algorithm works: I'm going to execute your little code of yours.
You wrote " Visually the behavior "makes sense", but what is the precise characterization in words?": right the way Maple fills non simple polygons make sense, at least visually. As it is easy to fill simple polygons in a non ambiguous way (because their interior does exist), it's not the case for non simple polygons.
Other common methods are based on drawing (for instance horizontal) parallel lines and swithing between "coloring" and "non coloring" as soon as these lines cut a side of the polygon.
But if you use this latter for the stellate pentagon
a := evalf(2*Pi/5):
p := [ seq([cos(a*k), sin(a*k)], k in [1, 3, 5, 2, 4]) ]
then a central regular pentagon should be kept white as it is colored. Probably it is what the intuition suggests, but it doesn't help to understanf the coloring algorithm Maple uses.
I implemented different ways to color general polygons and none of them offer the same appearance than Maple's does.
But maybe it's a vain quest for the interior of a non simple polygon is not defined?