A problem is NP hard if there are instances that other hard problems reduce to. That is, only some instances of the problem have to be hard. NP hardness says nothing about "average" problem instances and even less about hand-picked ones.
And that's what Sudoku puzzles are. They are made for humans to solve. They are specifically crafted to contain challenging, but possible, solution paths.
I was asking about why specifically it's surprising that humans are good at such problems. I think that to be surprising there must be some prior expectation about how good humans should be and then evidence that they're actually better than that. Both sides of that are interesting and I'd like to know more about it: What is the prior expectation of human capabilities here (and why), and how does it compare to actual observed capabilities.
I'm not sure sudoku is a good example since the problem size there is so small that I don't have any intuitive sense that it should be something humans can't do.
And that's what Sudoku puzzles are. They are made for humans to solve. They are specifically crafted to contain challenging, but possible, solution paths.