As soon as coins appear in a geologic stata they become the most common archaeological artifacts found from humans, and at this point we've got hundreds of billions of them spread all over the globe with many becoming lost in spots where even if they were submerged in water, they could easily still remain intact for hundreds of millions of years. Not all coins are inert, but many are, and many really are going to stick around millions of years. While volcanic heat and pressure can mangle inert metals, not many other natural processes will. There's no magical entropy that would cause inert artifacts in geologically stable areas that some coins would wind up in to just lose their form magically. In our world today there's a lot of stainless steel, gold, and other inert artifacts that are going to persist for hundreds of millions of years. It's not like there's volcanoes everywhere, nor do tectonic plates subsume everything - we've got Cambrian fossils after all...
Depends on the sort of water, I guess. Salty and oxygen-rich wouldn't be so good. I'll just leave the https://en.wikipedia.org/wiki/Antikythera_mechanism here for you to think about. That had ca. 2100 years +/-ca. 100 years of underwater seawater exposure, and look what it did to it.
What would only 10000 years more of that have done to it?
That's bronze. I'd assume any brass/bronze/copper to corrode away, that's what it does naturally. Now consider gold, stainless steel, and the many other inert materials humans work with. I assume 10,000 year old gold artifacts would look the same as the 5000 year old artifacts we know of which are very well preserved, and other similar materials would fare similarly.
