[Zikes]

Especially in certain situations like "I'm not very tired".

Offhand you could say "I'm not overly tired" or "I'm not too tired", but those could subtly change the meaning of what you're trying to say or sound unnatural in everyday speech.

[sliverstorm]

Both of those are modifiers as well, and could fall victim to the same overuse. The only surefire remedy is picking more words that describe a variety of degrees of tiredness.

Tired, exhausted, washed up, worn out, fatigued, beat, weary, run down, depleted...