For example, "John was asked to solve a complex challenge."
I find this to read very awkwardly, as if someone told me they solved a banana. Is this a case of verb-noun mismatch?
So long as the noun is something solvable, this would be a valid construction. Thus puzzles, Rubik's cubes and equations are all nouns which can be the object of the verb "to solve". So if the challenge was a puzzle, it could be solved. If the challenge was, however, physical in nature, it would be more natural to say that the challenge was completed. The answer to your question is thus "it depends on the nature of the challenge in question - if the challenge can be said to have a solution, it is acceptable to use the verb 'solve'".
I agree that it is awkward, and stylistically inadvisable. Problems are 'solved,' while challenges are 'met,' or 'overcome.'
The services company Halliburton's trademarked strap-line is "Solving challenges". I share the original questioner's queasiness with this but I suspect that the elasticity of English probably allows it.
"Solving a challenge" may not be linguistically correct. but it seems to be on the rise in a business or technical context (where "overcome a challenge" would sound slightly esoteric. An example I found is the Solve initiative initiated by the MIT (Massachusetts Institute of Technology) https://solve.mit.edu/challenges.
I am just confronting this in an article I am editing, and have opted for "find solutions to ... challenges". "Find a solution to the challenge" seems to be very widely used (more than 1.5 million hits on Google).