I have a shaky memory of seeing a programme that mentioned how the ancient Chinese may have discovered fossil remains of Protoceratops and explained them as Gryphon remains, and that the Leviathan who Perseus kills using Medusa's stare may have been fossilised Megafauna from about 10 million years ago eroding from a cliff. Unfortunately, I cannot provide a source, however, I would recommend looking at geological maps of whichever area you're interested in to determine the age of the rocks and then check to see what fossils could have been discovered as a result of this. Also, many medieval buildings have stone bearing visible fossils in their construction (from my memory Durham Cathedral and Escomb Saxon Church have this but there are undoubtedly more) but given the blasphemous nature of the implications arising from fossil theories, it must have been a cosmetic choice.