KQII begins with the newly appointed King Graham longing for a wife (I assume even kings get lonely with an empty bed). While wishing and wanting, the Magic Mirror clears and shows a woman in a tower, longing for someone to rescue her. Playing the hero, Graham decides that HE will be the one to save her... and he may have fallen in love with her looks.
So, Graham ends up on the beach in Kolyma... very quickly I must add. Soon after he arrives he meets up with a little girl in a red hood, looking for a basket of goodies. He walks to the mailbox of her grandmother's house, opens it, and finds the goodies. Now why didn't Red Riding Hood look there first? Knowing her, she probably put it there in hopes that the man to find her would be a handsome prince.
After helping Riding Hood (and receiving flowers as a thank you), Graham heads to the church. There he prays a short prayer and talks to the Head Monk. He was given a cross necklace to protect him from any vampires. Who says religion and prayer doesn't get you anywhere? As Graham continues on his journey, he comes to a bottomless chasm (or so it appeared, he didn't want to find out) with a bridge. Across from the bridge was a doorway with the inscription "Whosoever chooses to seek the key for this door will undoubtedly make a splash."
Sometime during his quest, Graham is attacked by a dwarf. In order to recover his treasure, he decides to head to the dwarf's home. What better place to stash your stolen goods then your own home, right? So, to a hollowed out tree goes Graham. Inside he finds a trunk with the stolen items and some additional treasures. Then, chicken soup cooking over the fire. Graham decides to take that also.
So, he goes back to the grandmother's house to talk to her... and discovers she's sick. What better cure for an ailment then chicken soup! As she eats it, she tells him to look under her bed for a large ring and an elegant black cloak. He leaves the house and heads towards the ocean. Didn't the inscription say something about a splash?
But, just as he's about to jump in, he sees a trident lying on the ground. He decides to return it to its true owner. He heads up and down the shoreline until, on a rock, he sees a beautiful mermaid. Graham, doing his best to impress her, gives her the flowers. She loves the flowers. She then calls over a seahorse for Graham to ride... and then she disappears.
Graham jumps on the seahorse and rides down to see King Neptune and return the trident. Long story short, Neptune was thankful and gave Graham the key to the door. Graham goes to the door, unlocks it... and sees a second door! "Whosoever chooses to seek the key for this door should set their sights high."
Graham wanders around Kolyma, trying to figure out what that means, and sees a cave. Walking in he sees Hagatha, a witch, cooking on a fire. Graham sees a nightingale, which he figured was the witch's meal, in a cage. He covers the cage with a cloth and sneaks out. As he's walking through Kolyma still, he sees an antique store. He walks in and sees a woman knitting behind the counter. Graham wants to get rid of the bird and cage, so he decides to give them to her... he didn't know that the bird had already been hers but was stolen by Hagatha! As a reward, the woman gives Graham a lamp.
He decides to rub the lamp, and all of a sudden a genie comes out of the lamp. The genie gives Graham a flying carpet, a sword, and a bridle. Graham jumps on the flying carpet and was taken to the top of a cliff. As he's exploring, a snake's blocking his path. Why Graham gives the bridle to the snake and not kill it, no one will ever know, but he did... and the snake becomes a horse.
Graham continues to the cave at the top of the cliff and finds the next key. He continues to the door and unlocks it... to reveal a third door! "Whosoever chooses to seek the last key must have a stout heart."
Graham remembers seeing a castle across from a poisonous lake earlier. He decides that it's time to explore it. To try to remain anonymous, he puts on the black cloak and the ring. At the "boat dock," there's a boatman waiting for him. He gets into the boat and travels to the castle.
Inside, he walks up through the dining room and decides to grab some of the ham. He continues down a set of steps to where a coffin is closed. Graham opens the coffin and sees a man sleeping there... Dracula. Graham grabs the tent stake and mallet he just so happened to be carrying and killed Dracula. Underneath the pillow was the last key!
Graham crosses the bridge, which collapsed behind him (maybe he should lay off the donuts?), and goes to the door. He unlocks it and walks through to an island with some amazing, non-normal colors.
Graham goes fishing and captures a huge fish. He lets it go and the fish offers him a ride to another island. In the center of the island is the Crystal Tower where he remembered seeing the beautiful woman. Just before he reaches the tower, he finds an amulet with the word "HOME" etched on it.
Graham enters the tower and walks up the stairs. However, the door to the tower room is being guarded by a lion. Graham uses the ham he took from Dracula's castle and feeds it to the lion. The lion falls asleep from a full stomach and Graham walks into the room.
The woman goes to meet Graham, she tells him her name (which is Valanice), he tells her his, she says she is forever grateful to him for rescuing her, they kiss, Graham says "Home" and the next scene they're at the monastery getting married. Back in Daventry, Graham takes his new bride into his castle. Next stop: the kids!