It is a very fun question to delve into. First off, humans as we know weren't alone in Europe when they arrived, Neanderthals were there. We don't know how they communicated, but they must have had some way, even if intuitive. However, for modern humans, I would imagine it wasn't so simple as one language, bearing in mind the size of Europe and distances involved between finds. For example, there would be a high risk of children being left with dead parents. High risk of death in childbirth plus high risk of death in hunting. This may well have brought a phenomenon of some people not speaking any language at all, and a massive regression. In small groups, it wouldn't be uncommon for them to make codes of some description. Essentially even if people were of the same race, it doesn't mean they liked each other when competing in similar areas. In fact, in a hunter gatherer society perhaps your brother is the biggest problem you have. Talking a similar language could have been the worst thing to do. There are many reason for codes, but one example of a current day code is in Listerland in Southern Sweden where they have different counting systems in a small area, made for fisherman to duck the former royal quota back in the old days. It meant you could talk at the dock and not have your neighbour tell on you. The utility of this is clear, and how often can this be developed? Twins often make their own language. Whistling, bird noises etc have all been used to communicate when reduced to a hunter gatherer paradigm. Aboriginies had over 200 languages when the English came to Australia, when the population was under 100,000. In a similar paridigm of life style, perhaps there were so many languages.
The grammar in some extinct Aboriginal languages was so strange and different from the English way of thinking, it is hard to say if we ever understood how they thought, regardless of what language they spoke. This is demonstrated to a lesser extent by a tribe in Brazil of about 300 people. A linguist was sent over (helpfully) to learn their language, and translate it into the bible. You'd have expected these hunter gatherers to be more grateful for this unsolicited gift of confusing fairy tales. The biggest problem was this culture didn't have writing, and didn't have a concept of the past. It brought the conversation down to this level, "Jesus is great and died for you." "Did you meet him?" "No." "Then stop telling us about him or we will kill you." The linguist wanted to reach the tribe on an emotional and spiritual level, which they didn't have, by explaining to them why he loved Jesus so much. His story went as follows, "When my auntie was very sad, she killed herself. The trauma of this..." "Wait, what did you say?" "My auntie killed herself." *laughter* "Why are you laughing, this was very sad for me?" "Why did she kill herself? That is the stupidest thing we ever heard."
These people were almost never depressed and couldn't understand why someone could kill themselves because their lives were so busy and focused in the moment. They had wild animals or other tribes try to kill them, but kill themselves? Ridiculous.
Perhaps the languages of the original people who came to Europe might not have made sense to us because their way of life was so different. They likely would have navigated by the stars, and thus much of their explanatory language may have been about star locations. Their beliefs were probably quite different too, if they had certain ones.
An example of this is Druidism. This belief, similar to modern scientology, is that the soul can pass into infinite bodies and lifetimes. There can be more than one soul in a body at the same time, and when the body dies you don't die. By this virtue, why did human sacrifice matter? In fact, why did dying yourself matter?
With these concepts of life and death, would all people have talked in a way we understood even if we could translate it?
In Plato's story of Atlantis, he states that people had to start again, as if like orphaned children. Whilst there is no proof of Atlantis, it is a useful philosophical tool to imagine not having something you once had, and not knowing what that was. It is a bit like putting paint on your hands and trying not to get it on your face, you realise how often we do things that we don't need to do unconsciously. Perhaps the meme of modern language is something we believe we need to achieve certain tasks, when in fact there are 100 other ways of communicating. Elephants, Prairie Dogs and other animals have interesting languages which are nothing like Human constructs of what a language should be. A prairie dog can communicate a person is coming, how big they are, what colour clothes they wear and if they have seem them before in one sound. What if humans once could do something like this? Elephants communicate up to five miles away by low noises we cannot hear. What if we did something similar with a percussive sound like a drum, afterall the Native Americans put their ear to the ground to hear a stampede.
If we can communicate in morse code, touch (braille, death dumb and blind people...) in sign language, with drums, in light, in smoke, in harmonics, in whistles etc, perhaps languages could have been like this. Maybe that is why there is no paper trail, because people explored other ways of communicating where writing was simply an abstraction.
