The effect of starvation in Brogue is identical to the effect of poison, although the two can stack: Your natural regeneration shuts down and you lose one point of health every turn. Rings of Regeneration no longer work.
When you start to starve, explore as much ground as you can as quickly as you can. Eke out your potions of life. Break out the wands and potions and scrolls you were saving for later -- anything to make monsters and traps stop bothering you so you can find food.
If you can get a health charm to +7, have drunk at least 2 potions of life, and have an ally to fight for you, you might be able to survive until you find food.
Starvation damage is not blocked by protection magic. Allies that can heal you will be able to keep you alive despite starvation, however - in fact, this is the basis of the oxygenarian challenge game.