Do you have specific cases of the alternative in mind here? I can’t think of a premodern state offhand that I know to have been founded by consent of the governed rather than an armed elite asserting its right to make the rules. IIRC Locke never gives historical examples; as Britannica says, “The more perceptive social-contract theorists, including Hobbes, invariably recognized that their concepts of the social contract and the state of nature were unhistorical and that they could be justified only as hypotheses useful for the clarification of timeless political problems.”
Giving a relatively small group of landowning and slave-owning military elites a monopoly on that power is hardly the only natural way of coming up with and enforcing social rules…and yet that is, with remarkable regularity, the form of the early states we see cropping up after the production of agricultural surpluses becomes possible. I think there’s a very common (though probably not universal) power pathway here, and it doesn’t look particularly Lockean or consensual to me.
If anarchist anthropology isn’t to your taste – though both James Scott and David Graeber are terrifically readable – you could look to public choice theory. Mancur Olson’s last book talks about the incentives a “roving bandit” has to settle down into a “stationary bandit,” i.e. warlords becoming dukes or kings, and offering their victims some predictability in how they’re plundered by turning raids into a system of tribute. It’s a theoretical framework, no less than Locke’s, but has the advantage that I can think of a dozen actual historical cases it describes.
Even if Locke’s theory didn’t describe the historical origins of a single state, that wouldn’t rob it of value. Living as we do in a world of states, it’s good for us to insist on states that take their legitimacy from the consent of the governed, defend rights and property, make rules based on the common good, and all the other stuff that comes out of the social contract framing. But if we let Locke’s story lull us into thinking any of that is natural, rather than the fruit of a hard-won struggle to liberalize the state, we’ll be more vulnerable to state oppression and to wielding coercion thoughtlessly ourselves.
Difficult but not impossible, I think. Let’s see if I can write that in a way you find plausible. 