Depending on the surrounding text, the meaning should become clear. (My personal impression, hearing it completely on its own, is that pretty is the adjective and egg box is the noun—but it certainly doesn't need to be interpreted that way.) I expect that if the term pretty egg box were found within several sentences, it would become obvious if it was referring to an egg box that was pretty or a box for pretty eggs.
Punctuation, as you suggest, is not necessarily wrong when it comes to grammar. However, the reception of such punctuation may be just as bad (or worse) to a reader as the ambiguity of not using it.
Although this kind of thing is open to subjective opinion, I can't quickly parse a pretty-egg box. I can understand its unambiguous meaning (because it follows rules of punctuation I'm used to), but I have to pause and consider it for a few seconds.
Perhaps a more quickly understood form of punctuation would be a "pretty egg" box. There is no hyphen being used in an odd (although correct) way, and the quotation marks serve to more easily distinguish the parts of the phrase. While this, too, is unusual, it seems more readable to me.
But I think the best option would be to let the context determine the meaning—or to simply rephrase it.
In theory, any such phrase could be considered syntactically ambiguous. However, usage and context will seldom result in any confusion.
Unlike egg box, which is not a defined compound noun, consider letter box, which is. (Although I could argue that even though egg box is not found in a dictionary, it's still treated the same way, informally.)
As such, even syntactically, the phrase red letter box is unambiguous. What's a box for letters? A letter box. It's a defined phrase. So, a red letter box is a letter box that's red. (Not to be confused with read letters!)
If you actually mean to describe a box for red letters (I suppose letters written in red ink or on red paper), it could, technically, be a red letter letter box. But that's simply awkward.
If context can't provide an unambiguous meaning (or if arguably correct phrasing or punctuation is awkward), then just rephrase.