They probably had at least some contact with those lands.
Dorwinion is a land adjacent to the Sea of Rhun, at least according to this map by Pauline Baynes:
And the Elves of Mirkwood, at least, drank wine which came from Dorwinion. From The Hobbit, Chapter 9:
"Now come with me," he said, "and taste the new wine that has just come in. I shall be hard at work tonight clearing the cellars of the empty wood, so let us have a drink first to help the labour." [...] It must be potent wine to make a wood-elf drowsy; but this wine, it would seem, was the heady vintage of the great gardens of Dorwinion, not meant for his soldiers or his servants, but for the king's feasts only, and for smaller bowls not for the butler's great flagons.
Dorwinion, or Dor-Winion, is also mentioned as a source of fine wine in The Lay of the Children of Hurin, line 230:
There baked flesh and bread from his wallet
they had to their hearts’ joy; but their heads were mazed
by the wine of Dor-Winion that went in their veins,
and they soundly slept on the soft needles
of the tall pine-trees that towered above.
In an unpublished essay, which can be found cited in various places on the internet, Tolkien said that:
[Dorwinion] was probably far south down the R. Running, and its Sindarin name a testimony to the spread of Sindarin: in this case expectable since the the cultivation of vines was not known originally to the Nandor or Avari.
This suggests that Dorwinion was inhabited at least partially by the Nandor or the Avari, and perhaps (but not necessarily, given the spread of the Sindarin language) also the Sindar. All three of these groups consisted of Elves who did not complete the Great Journey to Valinor.
Now the Silvan elves of Mirkwood were descendants of the Nandor, who, despite not having gone all the way to Valinor, were still among those who left Cuiviénen. You say "specifically, the Eldar, not the Avari", without mentioning any of the other groups of Elves, but I'm guessing that you'll count the Elves of Mirkwood, who dwell much further east than Rhun.
So we know that at the least, there was trade between the western Elves and the lands around Rhun. Anything more than that will, I think, be a matter of speculation; as far as I can tell, none of Tolkien's writings describe Elven expeditions to the East, but nor do they say that such expeditions never happened. And there's a lot of discussion on the internet about this and related issues:
The fact that there is so much discussion and speculation indicates that there's no 'canonical' answer, beyond the pieced-together facts about Dorwinion which I've outlined above.
(Some of this answer is based on the same idea - Dorwinion - as Riker's now-deleted answer. But I've provided a lot more evidence, links, and quotes, so I think I can safely say that this answer is my own work.)
