I don't think there is any paradox involved. The word "meaningless" has meaning as a word: "lacking meaning". Hence, it is clearly heterological, because its meaning cannot be applied to the word itself, just as the meaning "long" cannot be applied to the word "long" (because it has only four letters).
I understand what you mean by "codes" and the meaning of "meaningless" and can agree with that. But I fear that logically saying "meaningless has meaning" or "meaningless is meaningful" would result in a similar example of Grelling-Nelson paradox, which happens to the pair--autological and heterological. Maybe there's no paradox, it's just that I haven't thought it through~
Not everything is meaningful, therefore, "meaningless" is meaningful and not autological. But meaning depends on the code being used, and it is human to seek meaning, and therefore to presume the existence of codes we can understand. No one who did not believe in the Virgin Mary or in the ability of spiritual entities to manifest themselves physically in quotidian objects would ever see the BVM in a certain configuration of pancake syrup, which would then be for them meaningless, despite the best efforts of the Mother of God. I am a devout believer in the meaning of "meaningless".
I can agree with your dislike about the word-formation. I think I'm not wordie enough to find what they are using in cognitive science now. However, I do think what Mr Shermer means by "meaningless" is about the absence of physical/mathematical meaning, or physically significant meaning, except using one's imagination~
You may ask whether "meaningless" is autological, or whether "meaningless" is meaningless, that's a good question, but that's linguistics~
If one finds meaningful patterns in something, how can that something be called meaningless? Is meaning exclusively the product of intention, or do we create meaning by perceiving? If a person sees the image of the Virgin Mary in the syrup on a pancake and takes that as a sign of grace, which subsequently transforms this person's life, was the configuration of the syrup meaningless?
Personally, I don't like the word patternicity, which from the -ic-ity suffixes one would expect to mean the property of tending to possess pattern, not that of tending to perceive pattern.
I'm surprised that cognitive psychologists don't have a term for this notion, since pattern perception is such an intrinsic part of learning. Or perhaps they prefer to use words that are simpler but clearer, if less arcane, like "the tendency to perceive patterns." Or perhaps, they just call it something cumbersomely German, like Gestaltwahrnehmungsfähigkeit.
Michael Shermer defined it in the December 2008 issue of Scientific American as "the tendency to find meaningful patterns in meaningless noise". For more see here. An indeed interest idea, but I don't think it's brand new, even though I couldn't find any precursing phrases with similar meaning~