Mario most definitely does not need to be kiddy. In fact, I would argue that the old 2D Mario games, as you stated, were completely not. These games were presented in such a way that left a lot of the storytelling up to the interpretation of the user (something Nintendo still does) AS WELL AS leaving the interpretation of much of the themes, character development, and other areas into the hands of the players. This really goes for the rest of old Nintendo as well. Everything was presented in a manner that all ages could enjoy without feeling the childish tones.
I believe part of the problem comes from the fact that as technology has advanced, developers can put more of THEIR OWN expression into the games. The more expression and themes that are thrown into a game, the less that is left up to the interpretation of the player. That's why people can enjoy and interpret the early Zelda and Mario games to their mind's happiness, but the new games have more detailed graphics, characters, and themes that are pushed in your face. Nintendo has to hit those themes just perfectly to appeal to the masses, or they have to design their games around a more interpretive way again.
I kind of felt they did that well with Majora's Mask. That game had such immense depth and so many ways to see the game depending on how deep you wanted to dive into it. I also feel like Super Mario 64 did this beautifully as well. My hardcore BAMF uncle who loved to drink, smoke, and surf loved playing SM64, and I as a 7 year old also loved playing it. It was fun and accessible in a manner that didn't push and force strong elements that felt age or demographic restrictive.
(Yes, most of this was copy/pasted from my wall post).