Masks Link would be the best Zelda addition.
It'd allow them to rep Young Link again (outside of Toon Link, I mean), and by allowing him to transform into his Deku, Goron and Zora forms, you'd represent three prominent races in the Zelda universe. It'd work like Pokémon Trainer and add a great deal of color and variety to the roster. Plus... His Final Smash would be Fierce Deity Link! Would also be nice foresight on their part, if they plan to release Majora's Mask 3D at some point.
Regarding Pac-Man... I believe he's in the game.
Shortly before E3, someone posted here on GAF a prediction that Villager, Wii Fit Trainer, Mega Man, Little Mac, Mii and Pac-Man are in the game. As you know, Villager was confirmed, despite Sakurai having previously ruled him out, and not many people guessing him. And
nobody guessed Wii Fit Trainer. The post was not edited, either. The time stamp shows it was made before E3, and not tweaked since.
In addition... When one media outlet interviewed Sakurai at E3, they asked about Pac-Man, and Sakurai coyly replied with a question of his own: "How would YOU implement Pac-Man?" And the interviewer -- maybe it was Richard George, with IGN at the time -- said he'd go the classic route with the black eyes, and for his Final Smash he'd power up and chase the others around the screen like classic Pac-Man. Sakurai agreed it was a good idea. The implication, it was said at the time, was Sakurai was already thinking along these lines.
The thing about Pac-Man is he's one of the most well-known videogame characters of all time. He's an ICON. The legacy factor alone justifies him. Aside from being one of the great-granddaddies of the arcade scene, right up there with Donkey Kong, Pac-Man has some quality offerings in the here and now -- the Championship Editions are excellent, and for Nintendo's part, he continues to star in the arcade Mario Karts, and previously headlined Pac-Man Vs., the darling of Miyamoto's eyes and the Nintendo game that would serve as a prototype for the WiiU's defining feature (asymmetric play).
Consider also that Pac-Man is the mascot of Namco, which is lending an unprecedented level of support to the development of this game. The stars are all in Pac-Man's favor.
What about his move-set potential? He can launch himself forward like a human cannonball. He can dribble himself like a basketball. He can chomp and chew enemies before spitting them back up. He can spit out pellets like watermelon seeds, or belch up ghosts. Best of all, he could tuck in his arms and legs and "wakka wakka wakka" through the air, moving like classic arcade Pac-Man. You could even alter his flight path by 90 degrees, making him go up, down, left and right -- altering his path mid-flight to pursue fleeing enemies.
There is PLENTY that could be done with Pac-Man. Trust me, if Sakurai could figure out a full move-set for Wii Fit Trainer (and he has), then he can easily devise a compelling move-set for one of gaming's most well-known and best-beloved mascots.