Homo sapiens mostly didn't leave Africa until about 100k years ago, but when dealing with these things there is always a fair amount of uncertainty so some could have left much earlier.

There are also other early human species besides Homo sapiens that could in theory be responsible for something like this.

Homo erectus was galavanting around the world perhaps up to 2 million years ago, and they were tool users. Homo heidelbergensis was on the move around 600k years ago. Homo neanderthalensis was out of Africa around 300k years ago.