Very interesting question. I'll have a go at it, although these are 30-second thoughts: Pain is a warning system, very strongly correlated with damage and/or danger of death. Damage is bad, hence when we feel pain we want to stop whatever is causing damage; this has the incidental side effect (usually) of stopping the pain as well, so it feels as though we want to get rid of the pain - in other words, it feels as though the pain is bad, although what we really want is to stop the damage. A fitness-maximiser would want to stop the damage without the intervening step of pain.

With that said, though, I appear to have moved the question without really resolving it, because why is damage bad? Why is death bad? I don't think these can be answered without appeal to the plain utility functions: DO NOT WANT. So at best I've resolved the problem with masochism (edit to add: as a counterexample to people wanting to avoid pain), in that it's a rare BDSM scene which intentionally inflicts actual damage - piercings, at most. Accidents do happen, but intentional damage is very rare.