Other puzzles that should be mentioned include the gnome being given the spinning wheel for the marionette, and the tailor being given the golden needle. Yes, they both have a sort of logic to them: gnome + spinning wheel is a fairytale trope, and if you find a needle then you might think you could trade it with the tailor, who is presumably a kind of needle expert.
The problem is that both puzzles are weirdly backwards. You see the cloak and the marionette and ask if you can have them, and are denied. You have no idea how to get them. Once you find the spinning wheel and needle, and give them to their respective owners, only *then* do you learn that yes, the gnome lost his spinning wheel which, as it turns out, is valuable enough to trade for the marionette, because, now that you mention it, it can spin straw into gold. With the needle, it's only after giving it to the tailor that he tells you he 1) lost the needle and 2) happened to be walking by the inn a few days ago and must have lost it there. What annoys me about these is that the information is there - all the backstory needed for the player to solve these puzzles with a minimum of headache is there in the game. But you only get at it *after* you've solved the puzzle, which is ridiculous. In particular, the needle puzzle is absurd because you have no idea that you need to search the haystack: it looks a lot like a bit of the background. And yes, needles in haystacks is a well-known trope, but the existence of the needle isn't even acknowledged until you've already found it.
Also, I'd like to point out that I was completely stuck in KQ4 and 5 at the point where you're supposed to explore the sea and the desert. In KQ2, the sea formed a barrier to the west which was impassable; in KQ3, the desert performed an identical function. So naturally, when I find a sea or desert to the west, I assume the designer is telling me, "Don't bother going that way". It would have been nice if I'd been given a hint along the lines of "There are meant to be bandits in the desert; they might have something useful!"