The association of bears with honey as a kind of “general knowledge” is an old one, at least as old as the medieval bestiary tradition. The Aberdeen Bestiary (c.1200), for example, has this to say:

Insidiantur alvearibus apum, maxime favos appetunt. Nec avidius aliquid quam mella captant.

They attack beehives and try hard to get honeycombs. There is nothing they seize more eagerly than honey.

In terms of textual transmission, it isn’t exactly clear where this idea should have come from, as it’s not in any of the bestiary’s major sources. Isidore of Seville, one of the sources, does say in his seventh-century Etymologiae (XII.ii.40) that badgers (meles) may be named for their love of honey (mel). Perhaps there was some conflation in the intervening centuries (particularly, as noted in another answer, because bears really do sometimes eat honey)? Another medieval encyclopaedist of the natural sciences, Bartholomaeus Anglicus, gives an unusual account of the hunting of bears in his mid-thirteenth-century De proprietatibus rerum (which can be read in full here) and makes reference to honey:

the bear findeth honey by smell, and goeth up to the place that the honey is in, and maketh a way into the tree with his claws, and draweth out the honey and eateth it, and cometh oft by custom unto such a place when he is an-hungered.

Bartholomaeus attributes this to Theophrastus, who in turn is supposed to have learned it from bear hunters in Germany. According to Sharples, Huby and Fortenbaugh, Theophrastus of Eresus: Sources on Biology (1995), however, this isn’t a genuine attribution. Exactly where Bartholomaeus got this idea is unclear; it isn’t in the Plinian or Aristotelian sources of the rest of his entry on bears, but he’s unlikely to simply have made it up. Regardless of the ultimate source, De proprietatibus rerum remained a popular reference work for centuries, and was eventually translated into English by John Trevisa in c.1400. This, combined with the popularity of bestiaries and the spread of bestiary lore into medieval manuscript images like this sixteenth-century example may have helped perpetuate the idea in Western Europe – particularly for those without first-hand experience!

Bears are omnivores, and as a general rule they eat more-or-less whatever we are able to eat - although in most species this is biased more in favour of plants than meat. They do eat honey; it is rich with sugar and well worth the effort of obtaining it. People may have seen a bear indulging itself in a bee-hive and this stereotype may have arisen simply because there are relatively few species who are willing or able to attack a nest of bees and access honey - at least in Europe.

Although, as you rightly point out, adult cats are lactose intolerant, they love the taste of milk, probably because of all the fat it contains. In the wild, kittens would suckle for a certain period and then, once weaned, they would never see milk again. There aren't really any places in the wild where milk is accessible beyond infancy, so there was never any need to develop an instinct not to drink it; in their natural environment, they would never encounter it, and an instinct to avoid it would be a waste of resources. People would have noticed that they seemed to enjoy the taste, and perhaps didn't make the connection with subsequent illness because the cats spent almost all of their time outside and the symptoms would not have been very obvious to the people feeding them.

As for mice, I wasn't sure, so I had a look around. I did not find a citation for this, but one idea is that in medieval Europe, although mice would have eaten any food they could get at, cheese kept particularly well and lasted longer, and so people noticed the effect of the mice on it more than they would anything else, because the total percentage of the cheese consumed by the mice ended up being more. Flour and grain also kept well, but it is easier to notice nibble marks in a piece of cheese than a slight decrease in a pile of flour. I should reiterate that those are just suggestions I have found, and although they seem plausible I am not sure how true they are.