If it was set in stone that nothing on this planet was edible but the flesh of the native sentient creatures, I would go to them and do my best to ask them if I could have the flesh of condemned criminals, or other recently dead if it were culturally okay. I'd do whatever rituals/etc. that they demanded be done, if they had some sort of procedure for respecting the dead, if that were their requirement. I would make it clear that I would leave their planet as soon as I could, to go back to where I could survive without this.
If there was no way home and I would have to murder to live, I would ask them to provide me with as painless a death as possible, rather than starving or slow poisoning.