There is absolutely nothing in the movie to indicate where they are from. Morgan Freeman's monlogue at the beginning doesn't say they're from another galaxy. Instead, the visuals in the opening monologue seem to indicate a sphere near earth. Sounds like Mars to me.
I think you'll find in the fossil record organized, intelligent hominid gatherings in the Great Rift Valley (making and repairing stone axes in a factory-like manner) that can be dated to well over 2.5 million years ago. These would be Homo erectus, not H. sapiens, mind. The argument of tectonic plate movements etc is pretty much moot: tectonic upheaval happens at the edges of plates 99.99% of the time. We don't have intraplate tectonic events but seldom. Even then they are fairly localized. The last major one appears to have been the volcanic event that created Yellowstone, and that was well over 600k years ago. More recently, there's been magma wellings in the last two centuries in Missouri and Mexico, but those were extremely localized.
Personally, I'd say that the martians planted their machines well in advance to be ready to secure foothold when they were done with Mars. They would only have to have planted the machines a few HUNDRED years ago. Who had radar or had satellites watching every inch of the globe in 1632? No one. Keeping in mind that humanity CURRENTLY covers approximately 3% of the globe, there's a lot of land out there that remains for all intents and purposes terra incognita. In the 1600s, especially right after the Black Plague raped all of Asia and Europe, killing a signifigant percentage of ALL humans on the planet, there would be ever so much more open space. Artificial meteors with self-constructing ship seeds could be launched from Mars to impact on Earth. They would bury themselves, and the only thought would be "hey, another falling star". Ogilvy was under stress. He doesn't know if the Tripods were under the ground for 10 years or 10 million years. When he said 'millions', he was saying it in the sense of 'a large, finite but indeterminate quantity'.
Why didn't we see them coming to MAN the Tripods? Don't be ridiculous. Anything launched at the Earth from Mars on most trajectories will get to cislunar orbit without ever being detected. The most recent series of Earth rossing asteroids that we know about were only detected AFTER they passed Earth. If we can't detect a rock the size of thirty city blocks, I think we'd probably miss that low-albedo ship on a ballistic trajectory. Any number of small objects the size of a dump truck could be orbitting the earth right now and no one would know. Zero.
The final and perhaps most important point is the idea that we've been 'scouring' Mars for years. We've only been looking at Mars for a short time. Sure we've sent a handful of probes there, and even dropped five or so landers on the planet, but we've hardly scoured the surface and we haven't even looked at subterranean Mars. Any species sufficiently advanced to set up this centuries long plan, probably did their launches when our satellites were on the far side of the planet, from underground launch complexes (pure speculation, but hey, they've been watching us long enough to prepare a ridiculously powerful invasion).
