"NO LETTER PAPER" is the best of your suggestions.
The "LETTER" part was meaningful, because it meant the "LETTER" size, as opposed to some other size. "PC LOAD LEGAL", for example, is another message it displays.
Technically PC is meaningful as well, as distinct from the side-feed tray, say. It's just a dreadful acronym because, in an office IT context, no one thinks "ah, that's the paper carrier".
Probably they could have just omitted it entirely and let the use work out which paper source was empty. After all, since not everyone knew what the message many at all, that's what they did anyway!
The "LETTER" part was meaningful, because it meant the "LETTER" size, as opposed to some other size. "PC LOAD LEGAL", for example, is another message it displays.