I guess anything goes if it helps with the scenario, the bonus of a decentralized colonization would also be nice and I wonder if the papacy could be strong enough to organize such a thing, maybe papal involvement in such matters could start in an a scenario where the Franks are not hegemonical like you envsioned but where the papacy seeks naval support from Visigoths and Christianized Norse groups against Muslim raids and to remove Byzantine presence in Southern Italy or trying to remove trade dependence from the Near East or Byzantium.
I suspect if any power is strong enough to do this, it is the Papacy. The Merovingian kings and the Visigothic kings will have the demographics to sustain this, but the Papacy will have the power to unite the realms. The major question is, will the Papacy acquire power over the Visigoths for which to force a united effort between them and the Franks. My opinion is a no. This though is not necessary, the Visigoths can be used as part of a North African push and likewise the Papal sword into the Mid East. The Franks by contrast will be the vault to the north, defending from the Norse prior to conversion and also managing the affairs of the majority of Latin Christendom's population. This population may become too large under a massive Merovingian empire that lacks internal wars and lacks Crusades afar or colonization to the east. Say many of the Slavic states to the east convert peacefully and the Papacy protects them, making the Frankish borders become France, the Low Country, Austria, Bavaria, the Rhineland, and Germany the rest ending at the Elbe, say at Hamburg downward. This is a truly massive demographic power and one with enormous potential, far exceeding the demographic pull of the Spanish empire, even in the year 1000 CE, such an entity will have greatly more resources than Spain.
Considering that no eastern colonization occurs, or is far less, we might see the Franks move west. Perhaps a colonization of Iceland or intermingling of itself with the Nordic inhabitants in early years. This would maybe be prior to a Frankish conquest of Ireland.
If a discovery is to occur though, the reason to go to it and colonize it, will have to come from the Papacy, the most powerful potentiate in the region. The Papacy may order some sort of Frankish push westward, but this will be chaotic, haphazard and the Papacy may lose interest in the long run if there is setbacks in the east. However, it is likely that the Papacy will wish to redistribute excess population outside of Europe, this will include Africa and ideally for atl, America.
Regarding transit, I am not familiar with naval prerequisites to cross the seas. However, the Franks are not far from Ireland if they can attain the necessary Papal sanction to conquer Ireland and possibly Scotland and other islands. This will allow the Franks to fire forth into Iceland, and henceforth toward Greenland and then to Vinland. The franks will have the demographics and the economic force with which to sustain a population movement if they have a reason, something that the Nords increasingly did not hold.
This all will be contingent upon Papal force though. If the Papacy is unable to induce movements and create preferred models of growth for its Latin-Germanic subjects, Europe will be unable to undertake these ventures, just as Crusades were impossible without the Papacy, so too would colonization.
to be fair charles was already on the rise before tours by 718 he had most power and by 731 he had killed many who opossed him with duke odo being the only real resistance against him the islamic raid helped him beacuse it weakend odo and gave him presitigue i still think Pepin or his child becomes king while sure they would not have the prestigue and aquitinane would be stronger i think it just delays them taking it .
"The Gothic kingdom in Iberia will also be a behemoth." depends visgothic spain in 711 was a sick corrupt country in the midst of civil war it would take time for it to recover maybe a dynastical change or some frankish lord taking the throne in terms of the crusades i dont see why heavy plows and the vikings improving trade and the little optimum would be affected by no islam in iberia so the social things that predated the crusades are still there they migth just manyfest in the continent or in africa
Well, my point is that the Gothic kingdom is a demographically powerful entity, regardless of its socio-political situation. Ultimately, it does not matter, in the future, the Papacy will attempt to place its hand into Iberia in an overt sense and will build up factions therein with the power to retake the power lost by the Baltid royal clan. The Papacy can use the Franks to do this if at all possible and would be preferred. After which, the Visigoths can be permitted to expand into Africa. In otl, the Papacy utilized the Frankish element for Crusades primarily due to this being the only demographic entity with which the Papacy could tap into for expansion, aside for the Norman element. The Papacy may be unwilling to mix Frankish and Gothic claims to Africa either, as this may cause division, as we know, the Papacy in otl was unwillign to give the same privilege to multiple kingdoms, so as to diminish infighting.
-------------------------------
@KingOnTheEdge
Well, the Franks already possess the military organization and skill with which to subdue in pitched battles any of the foes they encounter. The main question si for what reason they would seek to do so. This is where the Papacy comes in, as a the cosmological basis for Latin expansion in all fronts. As we see from otl, the Papacy was able to cajole and inspire low nobles and their retainers into traversing great distances for the chance at better lands and for absolution of sins. In this world wherein a Merovingii or massive Frankish realm strides Europe as a colossus, the need for low nobles to acquire holdings fitting their status and name is more important. The Papacy and the overall Frankish monarch must find areas to divert them. The most unlikely of possible examples, is someway to dump these into the New World and provide a pension to said travelling warriors in peasants and women from across the Frankish realm. Sensationalized peasantry in the Middle Ages displayed their willingness to traverse the Sea on behalf of their king or the Papacy, especially in the Frankish realms, surely they did so and did so across lands, they may do so even in this instance.
--------------------------
One major benefit to the Medieval mindset in colonization, is that Medieval Europe possessed a cosmology more revolved around an expansionism that did not pertain to monetary benefit, instead such monetary benefits were intermingled. This cosmological basis, had to do with the expansion upon all important fronts in an enterprise to 'restore order' and secondary to this, as evident by certain Papal sentiments, was the notion of uniting the world under a series of rulers originating primarily from the Frankish seed. Post 1414 Europe, did not yet have a world conquest cosmological basis, at least not as aggressive as the Medieval one and it was likewise, any amount that it did hold, was holdovers from that which the Frankish world possessed in 1000-1300.