Hmm. Fiddleheads maybe? Ferns are some of the oldest plants and you can eat the fiddleheads of any fern that’s not poisonous (but be careful, a bunch of types are poisonous).
Biology
This is a general community to discuss of all things related to biology!
For a more specific community about asking questions to biologists, you can also visit:
Araucaria araucana Monkey puzzle tree nuts
There's also Araucaria angustifolia (aka Paraná pine). Dunno if it counts as either a separated entry or same entry as the A. araucana, both are phylogenetically close to hybridise, and the genus as a whole is what's dino food.
Some pics:

(Yup, it's my cover picture. See the big tree?)

(Open and closed pines, full of edible nuts.)

(Pine kernels with and without the shell.)
I go crazy for those once May* hits — they're delicious even simply boiled, but they can be also prepared into dishes. (I even adapted Roman burgers to use those.)
*They actually start producing in April, but as there's a non-zero chance the pine nuts from April are from felled trees, I avoid it. The species is critically endangered; eating some nuts is not a big deal, but falling the tree is.
They actually start producing in April, but as there’s a non-zero chance the pine nuts from April are from felled trees, I avoid it. The species is critically endangered; eating some nuts is not a big deal, but falling the tree is.
Good to know! I'd hate for these to suddenly become a fad and then endanger the tree even more. Knowing about the issue ahead of time means that people might check for it when buying it
Must be morphologically unchanged since its fossil age
That's interesting. So, genetically it could be significantly changed, but shape-wise, it must appear the same? In any case, I'm thinking certain molluscs might work. Sharks also might fit the bill, altho AFAIK they don't fossilize well. Or, are there other gymnosperms beside ferns and Araucaria that could fit the bill? I suspect so...
Now, feel free to hate on this, but I've found GPT pretty useful for issues like this. Evidently, there's quite a few more candidates.