They had 2 unused spaces, total of 16 characters. There's nothing perfect that would fit, like "TRAY ADD LETTER PAPER" is too long. But, they could have scrolled something like that left to right.
"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!
