[Legolas]

Prior to the last century of the Second Age with the sinking of Númenor, my understanding is that the Americas would have been the far-far east in relation to northwestern Middle-earth (where most of the stories take place). Valinor, Tol Eressëa, and Númenor (later called Atalantë by elves) were the only lands west of Middle-earth, and prior to the Third Age the former two had been removed while the latter was destroyed (al a Atlantis).

It wasn't until then that the world was made round. Thus, any lands discovered by men sailing west from Middle-earth after the Downfall of Númenor would have already present in the far east, just now wrapped around. This falls in line with Tolkien's plan for his Arda to be an Elvish account of the early days of our own earth.

The Avalon link is there as well, as the chief dwelling area of Tol Eressëa was named Avallónë. It was the immortality of Valinor that the Numenoreans sought, just as men hailed the healing and restoration of Avalon in the Arthurian legends.

After its removal, men would eventually find something very different off to their west: what had always been the farthest east, in the opposite direction of their initial migration, a land much more undeveloped in terms of their ideas of civilization.

Native Americans would've had their place in Tolkien's timeline, only he didn't (and probably never would) fill in the gaps between the beginning of the Fourth Age and the present. He reckoned we might now be at the start of the Seventh Age (and that ages had gotten shorter since), so I would guess that the discovery of the Americas would have fallen in the Fifth Age or Sixth Age, or perhaps would've been the significant event heralding the transition from Fifth to Sixth. He always chose significant events to prepare Age changes, such as the destruction of Beleriand and defeat of Morgoth (towards end of First), the destruction of Numenor (towards end of Second), and the final defeat of Sauron and the dominion of Man (end of Third).