Interestingly enough starfish will actually shrink down to a smaller size if they cannot find enough food, however, in a 25 gallon tank there isn't going to be enough food for a traditional type of star fish to not starve, brittle stars and serpent stars are what lie in your future if you are to have any success at all. As for Nems there aren't any species that are available, that look good, that won't eat all of your fish, that can fit in your tank, that don't need chillers, that you even have a 25% chance of keeping alive as an experienced aquarist, Let alone someone who is new to the hoby, I urge you not to fall into the newbie trap of thinking that people are just being catious, give it some time.
Edit: Most star fish do not sift through the sand, maybe you could get a sand sifting star, I certainly know alot of people who keep them in nanos, but I don't really recomend them because I don't like having a predator eating all the critters that life in sand beds.