A harlequin shrimp will "likely" eat them, not 100% guaranteed though. The bad thing about a harelquin shrimp is if you want to keep it after it's done with the asterinas, you have to keep feeding it starfish as that is the only thing they eat.
Most people buy a chocolate chip starfish and cut off a leg at a time to feed the shrimp. Feeding the starfish a good meaty diet will allow it to grow the limb back somewhat quickly.