Hello ShipWrecked,
I feed my Harlequin shrimp Chocolate Chip (CC) starfish all of the time. One starfish will last about 2 weeks. Just drop the starfish in... My shrimp 'sniffs' the CC Starfish out and has them flipped-over and starts snacking in about 2 minutes!! A word of caution, CC starfish can feed on your corals, so only put 1 CC starfish in your tank at a time. Note that I had the idea to purchase 2 stars at once so that I would have a month supply of food for my shrimp, but the Extra starfish was free to roam my tank and started chowing down on my 'JF Jolt' SPS coral and I nearly lost my coral!!! Your Harlequin will keep the CC Star 'occupied' and not not let up until he's gone. So, your corals a safe after the shrimp starts eating.
If you can find a sand-sifter starfish, I understand that they are coral-safe and the Harlequins like them just as much. However, I have only been able to locate CC Stars when food is needed...
I hope this info helps.
Take care,
RobbyeD