The prophet is saying that from the city of David, Bethlehem, the house of bread, which was nothing but a few women and children, the promised ruler of Israel would arise. Notice the military context:
ESV Micah 5:
1a Now muster your troops, O daughterb of troops;
siege is laid against us;
with a rod they strike the judge of Israel
on the cheek.
2c But you, O Bethlehem Ephrathah,
who are too little [insignificant] to be among the clans [armies] of Judah,
from you shall come forth for me
one who is to be ruler in Israel,
whose coming forth is from of old,
from ancient days.
Footnotes:
a 1 Ch 4:14 in Hebrew
b 1 That is, city
c 2 Ch 5:1 in Hebrew
The word is commonly used of soldiers going forth to battle (or David battling a lion):

This should probably also be considered an allusion to this very similar verbiage:
[Jdg 6:14-16 NLT] (14) Then the LORD turned to him and said, "Go with the strength you have, and rescue Israel from the Midianites. I am sending you!" (15) "But Lord," Gideon replied, "how can I rescue Israel? My clan is the weakest in the whole tribe of Manasseh, and I am the least in my entire family!" (16) The LORD said to him, "I will be with you. And you will destroy the Midianites as if you were fighting against one man."
"whose coming forth..." is apparently taken by the ESV to refer to his birth in Bethlehem. However, (and I'm no Hebrew guru) the word is plural and is rendered in other translations as "whose comings forth" (IE: given the context, "sorties" or "military campaigns").
Interestingly the LXX has the plural of ἔξοδος, which normally refers to one's departure from life (IE: death).
Now, if I'm correct concerning this then this would be, I believe in a notional sense, similar to this:
NIV Revelation 13:8 All inhabitants of the earth will worship the beast--all whose names have not been written in the Lamb's book of life, the Lamb who was slain from the creation of the world.
But most important, I believe is the concern in the original question that perhaps the form of one usage of OLAM might tell us the meaning of a similar use. However, that isn't necessarily the case. Context is always the key factor.
The NET Bible renders Micah 5:2 like this:
NET Bible Micah 5:2 As for you, Bethlehem Ephrathah, seemingly insignificant among the clans of Judah--from you a king will emerge who will rule over Israel on my behalf, one whose origins are in the distant past.
That's about all I think we can load OLAM with in actual usage.
And if his military campaigns from OLAM then we must not imagine that his first battle was in eternity past. Surely there was no war on day one!
The point is that the exploits of the Messiah have been in the scriptures from long ago and in God's mind longer than that. To that agree all the scriptures.
UPDATE
It turns out that Zechariah prophesied that it in the eschatological victory of Israel and Judah it was appropriate to have the lesser tribes get the glory on this one, and the weakest will be as King David:
[Zec 12:7-8 NLT] (7) "The LORD will give victory to the rest of Judah first, before Jerusalem, so that the people of Jerusalem and the royal line of David will not have greater honor than the rest of Judah. (8) On that day the LORD will defend the people of Jerusalem; the weakest among them will be as mighty as King David! And the royal descendants will be like God, like the angel of the LORD who goes before them!