The "astrea stars" (generally known as Asterina in the hobby though they are actually Aquilonastra stars - as Asterina is a different genus of starfish in the same taxonomic family, Asterinidae) would be your best true starfish choice. Personally, I like them, but as mentioned, some people consider them pests because they tend to reproduce quickly and they might eat coral. If you want to get them, you can probably ask local hobbyists or fish stores for them, or you can buy them from places like eBay.
I've heard some species eat corals and others don't - I've seen convincing evidence for one species (a very darkly colored one), and one piece of somewhat convincing evidence for one different species, but the vast majority of these guys seem to be at least mostly safe.
With regards to whether or not the average "Asterina" (again, technically Aquilonastra - Asterina is a separate genus within the Asterinidae family) eat corals, it might be a species specific thing, it might be a you have way too many starfish so they're out of other food options thing, it might be they're eating the slime coat/mucus on the coral rather than the coral itself (see below), or they might just opportunistically eat unhealthy corals. Based on how starfish eat, it seems plausible to me that it may also be coincidental (i.e. the star goes to eat something off the coral and the coral just happens to be one that is able to be negatively effected by the star's everted stomach). Regardless, Zoas are just about the only coral I've heard about regular "Asterina" stars potentially going after (so them potentially going after a birdsnest coral is news to me).
A quote I like to refer to for this:
