I'm showing off some starfish today starting with these Asteriacites lumbricalis from the Raethian stage of the Triassic that were found near Dijon, France. They are classified as trace fossils since they are the resting traces of starfish that later moved on. From what I can find, the theory is that the starfish burrowed into softer sediment to protect themselves when stranded during low tides. The burrows were filled in with sand once the tide came back in and the occupants crawled back into the sea. They are found from the Ordovician onwards to today.
This blog touches on these fossils briefly and has a modern example as well (scroll down about 1/2 way).
There is a brief article on Wikipedia about Asteriacites with some other pictured examples.
I have some other examples that I wrote about previously Here.
These next two fossils are legitimate starfish that both come from the famous quarries around Solenhofen, Germany. The rocks that yield these fossils are dated to the Tithonian stage of the Jurassic. Both look very similar to each other but it seems that Sinosura kelheimense has thinner arms than Ophiopetra lithographica.
Thanks to Gery for the first two fossils.