It's really a personal preference. I think most people get starfish because they want to look at a starfish. I haven't tried one because I've read so many times how people can't keep them alive. If you like it, then keep it. But I think you need to target feed them a nice chunk of food once or twice a week to ensure they are getting enough to eat.
In my 66 gallon fowlr, I have about a dozen hermits, 3 big nessarius, 6 small nessarius, a cleaner shrimp, fire shrimp, peppermint shrimp that all work on detritus in my sand bed. But I didn't necessarily buy any of them for a detritus problem, I just love having a variety of life in my tank. If you are simply going for a single animal and nothing other than something to clean up leftover food and poop from your sand bed, I would say that a cleaner shrimp would be the most effective. But a 75 gallon sandbed isn't going to be cleaned by any one animal. So why not get a nice variety? You can easily toss in a half dozen nessarius snails and never have to worry about them. Why not start with that and see how effective they are. The other positive thing they do is aerate the sandbed by burying themselves.