Acanthaster planci in its current usage does not in fact refer to a single species, but a pan-Indo-Pacific species complex consisting of four deeply diverged clades (Pacific, Red Sea, Northern Indian Ocean, and Southern Indian Ocean; see Vogler et al., 2008). These clades reportedly diverged between 1.95 and 3.65 Million years ago (Pliocene to Early Pleistocene) and have genetic distances (8.8 to 10.6 %) equivalent to the distances between other sibling species of starfish (Waters et al. 2004). Vogler et al. (2008) propose that this speciation process was driven by sea level changes (Pillans et al., 1998), isolating populations.
Vogler C, Benzie J, Lessios H, Barber P, Wörheide G (2008). "A threat to coral reefs multiplied? Four species of crown-of-thorns starfish". Biology Letters (Royal Society) 4: 696.