My entirely layman and unsupported conspiracy theory about language is that early hominids likely developed complex sign language and some primitive forms of writing now long lost to time, but vocal language only came with the necessary biology.
The externalization of language, whether vocal or gestural, evolved later as a means of serializing the internal language in order to transmit those thoughts to others. Under this hypothesis, the serial nature of language is a limitation of the externalization methods (you can’t produce several words at once, or hear several at once), whereas internal language itself need not be a linear process.
We know from their remains that Neanderthals would have had a rather different range of vocalizations from Homo sapiens, but that doesn't mean they didn't have structured language.