How to make a limestone cave
The Jenolan caves in Australia are reputedly 340 million years old. Those caves are in limestone deposits that were formed on the bottom of a shallow sea in the Silurian or earlier.
Limestone is the most likely substance for these caves to form in. But limestone isn't really a natural geological rock, it is formed by the crushed shells of marine invertebrates. There can be non-biological limestone, but it is much rarer, and probably nowhere pure enough to form limestone caves.
Limestone comes primarily from corals and foraminifera. Both these species developed in the Cambrian, but did not become common until the Ordovician. I can't find good data on how long it takes Limestone to form from these invertebrates, but it is millions if not tens of millions of years.
Assuming a few millions of years of depositing marine shells, then a few million more years of limestone formation, then this continental shelf (limestone doesn't form in deep water under high pressure) has to become dry land, then that dry land has to get enough rain to expand a cave system...you are probably looking at Silurian era for the earliest limestone caves.
How to get a cave to survive
The problem with limestone caves is once they start eroding, they are likely to keep eroding. The Jenolan caves are conveniently located a drier part of the Earth that has always been relatively dry. Australia has never been too polar or to equatorial over the last 400 million years or so. Also, it has never been underwater either. The only other part of the world that I can think of that meets both these criteria is southern Africa.
Cratons are probably not possible for natural caves
I don't think a craton could potentially have many caves. First off, they have never been underwater, so they were never able to get a layer of limestone on them. Secondly, I don't know of any other materials components of a craton that would make caves like limestone.
Incidentally, this will then rule out southern Africa, since most of that sits on the Kaapvaal craton. Maybe caves would be possible in the sedimentary fill between the Congo and Kaapvaal craton (roughly Angola/Zambia)? I don't know much about the geology of the area, and there isn't much information available online.
However, if we are talking artifical caves, then the safest place to put one would be in the heart of a 3 billion year old craton. Cratons this old include the Kaapvaal in Africa, Dharwar in south India (partially covered by the Deccan Traps), Pilbara in western Australia, Superior under Minnesota and Manitoba, Slave in Canada's Northwest Territory, and Sarmatian under the Ukraine.
The Witwatersrand formation is an igneous plug in the Kaapvaal craton that formed 2.7 billion years ago and is pretty much still the same today. An artificial cave there could have probably survived all this time.
Based on the likely cave forming processes, the oldest caves would be Silurian in origin, and would likely be situated in Australia or southern Africa. Since the Jenolan caves meet these requirements, it sounds like they are about as old as caves can get.
For artificial caves, the possibilities are more significant, since there are igneous provinces on top of cratons that are more or less unchanged for billions of years.