Firstly, I very much like this question, it's this obscure, hidden kind of stuff that I most like within Tolkien's works.
After searching for an answer for some time now the only logical answer that I can give is that by saying "ever came to their country" Tolkien means Elves barely came to Dunland not just during the lifespan of the Dunlendings but ever since these people settled there in the first place.
This would make sense, since the ancestors of the Dunlendings, the Gwaithuirim who lived upon the Gwathló, surely must have known of the Elves living in Hollin back then.
As such, Elves wandering through the forests or on their way to Lórien around the Misty Mountains and not over the Redhorn Pass must have been encountered by the early Dunlendings, who perhaps feared them due to the perceived superiority of the Elves.
This knowledge would then have been passed down from generation to generation and would thus also be known in the form of myths by the late Third Age Dunlendings. They would then also fear the Elves and hide.
To me this makes sense since in M-e this often is the case - that old myths are still remembered by descendants. One example that comes to mind is the doubt of Eorl the Young concerning Lórien, also due to myths of that land being remembered within his culture as memories of when the Éothéod used to live in that area.
Then again, perhaps an easier answer exists...
