Here's what I suspect so far, but it's a bit kooky/incomplete at places:
These are all Super Smash Bros 4 characters
One evokes pizza
My best bet so far is Wario, since in the WarioWare series, there is a character Mona Pizza that sells...well you get it. There's also a song on WarioWare stage called "Mona Pizza's Song"
One fuzzy, maybe funny
This one I don't get. At first I thought Donkey Kong/Diddy Kong, but the clue implies it's a single character.
Spooks
Pacman & ghost co.
fruit or pork
Here I think this is Mr. Game & Watch. I haven't played him in SSB4, but in brawl, it was difficult to tell if what he was flinging in his neutral B was bacon or fish or what. Also one of his Side-B results (7, I think?) drops a healing fruit.
frog
Greninja is a frog Pokemon
Double letters (in Japan?)
There are a couple characters with double letters, but the Japan clue makes me more certain that it's Wii Fit Trainer (where Villager would not have double--or single--L in it's Japanese rendition and Wii is the Japanese name for the console)
Two known names; link them to solve
This was the clue that started it off for me, this seems to hint at Zelda and her alter ego Sheik. The inclusion of the word link reinforces this.
Bonus: This poem has link, too
Link himself is also a character in the game