Ah but we never started with barter. That's the myth the book goes into. The very earliest systems of money were all credit based. Money came about through war (you conquer an area, leave a garrison, force people who have never used coins to pay taxes, coins they only get from soldiers) and barter only appeared when a state failed.
Barter only exists in the void left by states. There is no evidence trading oxen for grain every existed. It's too small scale. Early pre-historical civilizations were more likely to be communistic where everyone helped everyone else (native american tibes were like this .. more like ant colonies).
Even when a barter market emerged, it semi-state like thing had to rise with it. It's a really good book; highly recommended.
I haven't read that book, but your statement about markets only existing with the state strikes me as very odd. Conceptually, no government is required for a simple barter system - you and I can simply agree to trade X for Y. Perhaps that is key point - if you want to use "money", then the state is required. Although even then you can theoretically just use gold/silver coins.