I wonder how would we react with tools dating back to, say, 5MY ago ...

That would shake our knowledge from the foundations.

No it wouldn't, as we already think it's pretty likely. Chimpanzees use tools, so our most recent common ancestor with them, something like 6 million years ago, may well have used tools too. https://en.wikipedia.org/wiki/Tool_use_by_non-humans, https://en.wikipedia.org/wiki/Chimpanzee%E2%80%93human_last_...

I don't think so, have you read 'The Bonobo and the atheist'? Humans are not the only ones using tools and in reality there isn't much difference between humans and animals. The conclusion I get from the book is that the only difference is religion. Although, I have a feeling that humans do have a more developed intellect (problem solving) but this was not explored in the book.

5 Million years ago would be insane... but what about..

5 BILLION years ago...