This sounds like 'The Intruder', a short story by Theodore L Thomas in the February 1961 issue of The Magazine of Fantasy and Science Fiction. However, the man isn't a time traveller - he lands in a small spaceship on what appears to be an Earthlike but entirely lifeless planet. (Lifeless unless you count things like trilobites; the man is on a fishing trip, spearfishing trilobites.) He camps by a waterfall, but suddenly notices a tiny lichen on the rocks, stamps it furiously out of existence,
Max glanced at the water's edge ten feet away. This speck of alga had been out of the water for fifteen days, and it lived and grew. It lived. Max's eyes widened. Here and now it had happened. It could have happened a million years from now, but it had happened now. This was the way it had been on Earth during Cambrian times 400 million years ago. A first plant, coming out of the water onto the land, and living there. The first fragile step on the road to man. There was no more to it than this, a bit of green growing on a speck of sand on an island of rock. An intrusion onto his clean and lonely rock. Max stared at the green spot six inches from his face, and his eyes watered in angry frustration.
He jumped to his feet and ground the little fleck under his foot, stamping on it and twisting his heel again and again, ripping the tiny cells to shreds, rubbing them against the rock and the sand until the spot was scarred and lacerated. He bent and brushed the muddy dust into a little pile and took it into his hands and strode to the water's edge and flung it out over the water.
and heads back to his ship, apparently intending never to return. I've never read the story since, and I remember feeling that I hadn't really understood it, possibly because I would have been about 13 at the time! The brief editorial header to the story was
A simple little saunter down a trail that Hemingway has walked before--with, however, science fiction scenery, and an unexpected turning. . . .
an allusion which I've never traced, either.
I can't find a link to the text, or any evidence that that the story was ever reprinted in English, except in Damon Knight's anthology A Pocketful of Stars, which surprises me, because I remember it over 50 years later...
The second story you mention was correctly identified in a comment by Jason Baker as "Tripod" by Les Cole.