banerjeea_98, you have to understand the use of past progressive. Past progressive means that an action was going on in the past at the exact time something happened in the simple past tense.
eg. People were walking briskly when the bus arrived at 6PM.
The bus arrived at a defined time in the past while people were walking(passive verb tense describing the setting in which the bus arrival happened in the past)
Applying this to the question at hand means that the "northern regions of the Middle East" arose over an indefinite period of time in the past while
"the first trenches" yielded some kind of evidence.
This is illogical as the two actions should be independent of each other.
As to qhoc's question "simulaneously with but independently of the more celebrated city-states", you just have to dissect the two elements linked by conjunction "but" to see why "with" is necessary.
[the more celebrated city-states
independently of the more celebrated city-states
Remove the "with" and you will see that the simultaneously does no longer link to "the more celebrated city-states" while the second element does.