He may also be supplementing himself with asterina stars already in your tank, but eating starfish is not a preferrence for them, it is a dietary requirement.
A shrimp won't look sick or skinny if it's starving, it will just continue to starve until it dies... /shrug
I'm not a biologist speciallizing in shrimp or anything, but all of my research on (and care of) these shrimp dictates that they need to eat starfish to survive.