you know, this is an interesting question, even if it does stray quite far from the characters and their appeal. nintendo characters are popular because they appeal to so many demographics, and appeal to those demographics because they're popular. one of the strengths of their franchises is that they're free from the things that normally alienate people... such as adult situations and sexuality. even innuendo is rare, if ever found in direct connection with them.
that said, to take them out of context and replaced into an adult context... we can all read whatever we want into it. gay characters are of course as much speculation as is assuming they're straight. do the male protagonists battle to free the damsel out of heroic duty, romantic interest, or a mixture of both? 2 of the 3 options imply heterosexuality, so the odds are in that favour, but this thread is to explore that other 1/3 chance that they're not.
that actually got me thinking about which characters are the most likely candidates, and as i was going down the mental list, it seems a fair amount of characters are in fact genderless. most enemies for example: birdo, goombas, koopas (minus the royal family) seem to reproduce asexually in some fashion; others who are specifically gendered seem to be one of a kind in breed, meaning they have no others in the species to mate with anyway. where is queen koopa? do queen gohma and king dodongo somehow interact? how does bongo bongo procreate? i think we can all deduce for ourselves the situation of Master Hand (super smash bros.).
other characters seem immediately identifiable as to which camp they belong. many gamers instantly peg tingle as the richard simmons of nintendo, but how can we be sure? twin rova from OoT... sisters, or check the box next to "other"? but those are human-like characters.
many nintendo characters aren't even human, which evokes the ever-long debate of whether homosexuality is somehow genetic or otherwise innate, or if it's a behaviour that is influenced by one's environment...or if that debate even applies to non-human life. do other animals or extraterrestrial life fall under the same rules as human sexuality?
or what about environmental physics? in the mushroom kingdom, gravity is obviously different from earth. humans can jump many times their own height into the air, as well as whole inanimate objects capable of floating freely. how does this affect nature, and thus, nature vs. nurture?
all that said, it seems we can only restrict our search to humanoid characters of earth or earthlike origin.
- mario? not likely. he is often seen with or chasing after women all over the place, including his 'girlfriend' from the early 80s, pauline.
- luigi? he could be, seems he's either much lonelier in the companionship department, at least to any extent we are shown.
- samus? no way. her hair is much too long
- link? sort of in the same boat as mario, but then he DID run away from babealicious Saria in fear of her 'advances'.
- zelda? seems to have some identity issues. between cross-dressing as sheik, and posing as pirate on a ship of men... she could have some secrets to hide.
- mr. game & watch? the title of 'mr' implies a possible counterpart of a 'mrs. game & watch', but it could also be a formality, since he's always dressed in that slimming, (metro)sexual black.
those are some of the rather short list of characters who we can actually make conclusions about from a scientific/societal standpoint (based on our own world and physiologies), and it's a very mixed bag. of course nintendo will likely never comment on twinrova as their own in-house version of 'bert & ernie', but that doesn't mean we can't have fun guessing!