"So, it would be fairly plausible for reasonably large, physically fit man to pick up a 4 or 5-year-old without undue difficulty, although he probably wouldn't want to carry him around for too long? Say, if the kid was injured, needed to be boosted over an obstacle, was being abducted by a ferocious cave troll in a game of pretend..."
That's very believable, especially since you're not talking about extended carrying, like picking up a tired child at a zoo, but just talking about a quick grab-and-lift. For play or a lift over something (or a situation which would warrant extra exertion like carrying an injured child), it's plausible for average people even up to about eight or nine years old. For "pick me up, daddy" stuff I'd say that five is about the top limit. It's not just weight at that point, it's as much because five-year-olds don't tend to like being carried for long distances as much as toddlers.