Trademarks are issued only for specific pre-defined categories. For example, computers fall within Category 9 (which I happen to remember from filing trademarks a long time ago). IANAL, but I do know a fair bit about trademarks from going through several applications and asking a bunch of questions.
Nintendo's Super Mario mark wasn't granted for the category containing supermarkets, so their registration doesn't allow them to stop anyone using those two words for a super market. But if a market were to also incorporate elements of the Super Mario logo, font or trade dress then Nintendo could pursue them for trading on the value of Nintendo's brand. Which is what you're referring to.
But in this case, the market didn't do that. Trademark law and the associated decades of precedent are actually pretty deep and nuanced. Even back in the 1920s people would try to skirt the rules and benefit from a strong brand's recognition without getting technically busted. So trademark jurisprudence has gotten surprisingly good at sniffing out these shenanigans. But by not using any other logos, colors or trade dress, the market is completely in the clear within their category.
It actually doesn't matter if Mario, the market owner, was being a savvy legal eagle and shrewdly planned to soak up a little of Nintendo's brand value or if Mario really did just name his super market "Super Mario". Trademark law expressly allows him to do that. And it's a good thing it does because granting mega-brands like Nintendo and Disney a monopoly on using simple combinations of common words is a slippery slope toward dystopia. It needs strict boundaries and limits. Mario's market isn't "getting away" with anything here. He's playing by the rules. IMHO, this wasn't even a close call. Nintendo's claim was obvious bullshit. They knew it was bullshit but filed it anyway because usually little guys just give up when faced with an army of high-priced lawyers. I'm glad Mario didn't. Instead, he asserted his rights under the law and won because he didn't do anything wrong.