Rock Lee and Guy-sensei from Naruto (aka Thickbrows and Superbrows).
Kisame's sword Samehada, especially when it's cuddling up to Killerbee.
White Zetsu and his brother Guruguru have this going for them. Despite being villains, both are quite childlike to the point of being Affably Evil. WZ only has half a face, but likes to joke around while Guruguru is a humanoid mass of tendrils whose obsession with poo keeps him from seeming sinister even when he is being sinister.
Gluttony's even cute when his ribs open like a zipper to reveal a giant mouth.
Also Sloth. He's huge. He's lumpy, fanged, and freakishly dangerous. He hosts blank eyes and a vapid expression. But something about his unmotivated, drag-your-feet mannerisms and simple speech ("Mendokusai...") make him look like a perfect candidate for a plushie. His big muscles just make him look huggable. His asymmetrical design brings to mind tears like a cheetah's face. He says, "Buh?" and the readers squeal, "So cuuute!" He gets spartan-kicked off a tall building into the snow after wandering around aimlessly in a military base...the fans let out an, "Awww!"
Quite a few characters from One Piece would qualify, especially Usopp, Brook, and Bearsy.
Oars Jr., despite his meteoric apparition, would qualify just in the same way as King Kong - A giant, green, gargantuan (he is at least three times bigger than your average giant!), demon-looking pirate with a soft heart (A typical run-of-the-mill Gentle Giant). He is shot, hit with a giant shockwave, had his leg severed and his heart was impaled by shadows while trying to save his friend who made him a hat that protected him from the rain.
And Marine officer T-Bone, who looks like a zombie despite being alive and well. But he's so compassionate and earnest in his desire to help people that he has the undying loyalty of his subordinates (even if they're a little creeped out by his appearance) and it's hard not to feel bad when the Straw Hats have to plow through him on their way to Enies Lobby.
For a female example, we have Kokoro's granddaughter Chimney.
Rico/Loli and all versions of Exedore/Exsedol from the Macross and Robotech universes, but especially the latter's first form.
Pen-Pen from Neon Genesis Evangelion. Seriously, it's not the prettiest penguin you've ever seen (he's got clawed wings, dear God!) but what counts is how endearing he can be, especially when you know why Misato bothers to keep him despite his flaws (like being a glutton, good-for-nothing bird).
Guilmon would fit here too. In reality, he would look far more terrifying than cute, but his childlike demeanor, antics, and voice just make him so adorable.
Renamon applies as well. The species is described in canon several times that they are tough and intimidating in appearance (especially their glaring eyes) that other Digimon become nervous or threatened by their presence despite the Renamon not intentionally trying to scare others off. This doesn't stop people, be it in the canon or in the fanbase, to still consider the race (especially female ones like Rika's Renamon) to be beautiful, elegant, cute, or (depending on who you ask) sexy.
Even better, L. The manga's artist, Takeshi Obata, said he was supposed to look ugly. And L has legions of fangirls.
Rem is also actually quite lovely in an odd way.
Gelus looks like an abandoned rag doll. Awwww!
What's even more awesome is that in the originl designs, Gelus was supposed to be an extremely beautiful Shinigami. Ohba, however, decided that making him The Grotesque would be better because Gelus is such a pathetic figure and the audience would relate to him better. He was right!
The snail youkai from Karas that accompanies Nue is a bit ugly, but also utterly adorable.
In-Universe example: Nyanko-sensei in his Maneki Neko form from Natsume Yuujinchou is constantly referred to ugly, "pig cat," "world's ugliest cat," etc. by nearly every character who sees him. Taki, as well as much of the fanbase, finds him absolutely adorable. The former's fangirling of him is seen as very odd by her peers and has become something of a Running Gag.
Bills, the main antagonist of Dragon Ball Z: Battle of Gods. His playful, cat-like nature is hard not to find endearing, and his appearance is based on a Cornish Rex◊, which would also fall into this category.
* Fat Buu, post heel face turn, goes from being a vinyl toddler-minded murderer to a heroic pudgy-faced well meaning manchild. His genuine naivete helps here.
Tomoko from Watamote. Admit it, her eyebags make her look cute.