Franks did not have a good navy because they never had any good reason for creating a powerful one.
All of their campaigns were in the continent and, pirates apart, the only main threat from the sea were the Viking raids, which happened mostly after Charlemagne's death. The main Frankish cores were not located in the coastlands (rather underpopulated during their time) and even the Vikings had to sail up the Seine river and other big valleys in order to attack important Frankish targets. Also Saracen sea attacks were not important until well after the death of Charlemagne.
If they had considered that a campaign against 'evil Pagans' in the neighbouring Isles was worthy of building a proper powerful navy they had probably done it, as they could count on the logistic and engineering help from the Byzantines for such anti-Pagan purposes.
But why would they decide to invest all that effort against the British pagans when they had the much wealthier and just as "evil" Al-Andalus just across their border? Building a fleet is not something one does out of a whim. There are better ways to expand. And as you said, the coastal regions were de populated. Building a fleet would need to go beyond building ships and into putting up the infrastructure necessary to sustain them. A very large investment the Frankish kings would probably prefer see go towards wars among themselves or to expand to wealthier lands than the rather impoverished Britain.
Besides, I'm not as optimistic in "could count on the Byzantines for anti-pagan logistics". Why would the Byzantines teach the Franks, the very ones claiming their imperial throne, how to assemble a navy, the one thing they have to defend themselves against their attacks? An anti-pagan navy can be used for non-anti-pagan wars. Any ruler would see they would be selling the rope with which to hang themselves later.
I don't like when people put Crusader mentality, a very specific aspect of a specific time in History, in the soul of every Christian, from the Crucifixion to Vatican II. The Franks used religion as a casus belli, yes, but they used it in the way that fitted their interests. Ultimately, fighting against their Christian enemies would take precedence over the pagans across the sea. It wasn't fanaticism as much as it was opportunism.
Speaking of which, it seems Charlemagne's missionaries in Saxony were mostly Anglo-Saxons. Would a pagan Britain make conversion efforts more difficult to man or would missionaries be sought from another region? And how could that affect local Christianity?