Sorry but your re-write is awkward:
The kids had scattered their books all over not only the bus but also the sidewalk.
It is the placement of "not only" that breaks the sentence up in the wrong place.
The original was perfectly acceptable:
The kids had not only scattered their books all over the bus but also the sidewalk.
It is constructed correctly, but there are usually many ways to construct a sentence and some will sound more natural than others. It all depends on whether you want a written sentence to sound formal or more how someone might say it.
Some alternative ways:
Not only had the kids scattered their books all over the bus, but all over the sidewalk too.
(I think this is most like how it would be spoken)
The kids had scattered their books all over the bus and the sidewalk.
(Less wordy, to the point)