Availability? Just type "Longevity" into NXP's site and you'll get a very good web page on just that:
https://www.nxp.com/products/nxp-product-information/nxp-product-programs/product-longevity:PRDCT_LO...
Filter on "32-bit Coldfire" and you'll see that they range from 2005 to 2010 with "10 year longevity" and ones from 2007 to 2010 with "15 year longevity". That said, we're still buying the MCF5235, which is a "2005 10 year" part. It looks like NXP will keep making popular parts that there's enough of a demand for.
"EOL", but possibly still available (except for the chip shortages). Don't ignore the sense of a "Last Time Buy" to get enough for that 5 year requirement. Maybe that should have been done a few years ago.
It seems to me that spending time on a "quick-fix substitute" might take resources away from "the replacement product". It might even take longer to get this one working than getting the existing replacement working. Unless the "Replacement" has fallen victim to the "Second System Effect".
There's no "drop in replacement" for the MC68340. Were you using the MC68340 or the MC60340V? The reason I ask is that AFAIK all the Coldfire parts are 3.3V. If the existing board isn't using the "V" (3.3V) part, then you won't be able to put a 3.3V ColdFire (or ARM) chip on the board with existing 5V parts. Everything else has to be replaced to get to 3.3V as well. Or you need "level shifters", and that's a pain.
The MC68340 has no internal RAM or FLASH, so it must be using external. How much? A little or a lot? Can you replace the CPU and RAM and FLASH with a Microcontroller with enough internal memory so you don't need any external? That would help to simplify the design.
There's another problem with starting a ColdFire design now. You can't get development boards any more. It is always better to start on a supported development board (with supplied code that runs on it), but you had to do that 12-19 years ago. If you just drop an unfamiliar CPU onto an existing board, debugging that can easily take a very long time.
You could emulate the 68k on a faster CPU if necessary. The MC68340 only ran at 25MHz maximum on a 16 bit external bus with a 2 clock minimum instruction execution time.
You could probably get away with a 5V PIC!
How "bad" is the existing software? How much is in assembly? How much directly accesses the hardware devices (instead of being abstracted via generic device drivers)? How much code is written assuming and relying on the big-endian byte order? So how much effort would there be in rewriting the existing code?
What about future support of the product? Does it need field software updates? Does it need to be repaired over the next 10 years? Can you get the spare parts to repair them?
There's no simple answers here. This is a "Real Engineering Project".
Tom