It is unlikely, IMO, in a tank with LR and algae growth with pods, for fish like clownfish to starve. One of the reasons to use LR is to provide a NATURAL food source to fish. Specialized feeders, or fish in FO tanks are at risk of starving. IMO, it is really truly rare for generalized feeders in tanks with LR (and new tanks with a clear sign of a nutrient issue) to actually be starving. I do not believe that is an issue. Feeding flakes twice a day, in a tank with LR, pods and some mysis every once in awhile??? Those fish are not starving, IMO.
I regularly hear of peppermint shrimp eating corals such as these. After all, it is not that far off - we put them in tanks to eat aiptasia, an anemone, a very very close relative of those corals. It is not surprising at all to me to be honest. BUT they will also readily eat dying corals. THis sounds like a young tank, and I don't believe parameters were posted. My first assessment is that the coral may have been dying, and the pep. cleaned up. Regardless it is possible it ate it otherwise also.
The reason you nitrates are increasing - apart from true issues with the test kits themselves - is the fact that it accumulates in most tanks while ammonia and nitrite are converted. So nitrate is the end of the road and it builds up until water changes or other export (algae) uses it.