Unfortunately this seems to be a regional problem. We have an iPhone XS Max, and iPhone 7 Plus, an iPhone XR, an iPad Pro 10.5”, and iPad 6th Gen and they all have the same issue ever since updating to the final versions of iOS 13. This continues even today with iOS 13.1 and iPadOS 13.
None of the devices is able to obtain even the simplest of directions in Cyprus.
Everything worked fine up until iOS 12.4.1.
Cyprus is still listed under the regions in which Apple Maps directions is available.
So this is either a major bug or Apple removed it on purpose!
Whatever the reason, this needs to be fixed ASAP! Or at least remove Cyprus from the available regions and issue an announcement.