Fruits and honey are not the only natural sources of sugar. Please don't
lose sight of the starchy root vegetables, which are generally available in
abundance and are well represented in the diets of modern native cultures.
I don't believe that carbs were unavailable, unknown, or difficult to
obtain in paleo times.

Of course Twinkies and Froot Loops had not yet evolved in that era.