I was actually considering making a thread about the possiblity of a state that manages to unify the peoples of the Horn of Africa building an intricate irrigation system on the southern (mainly southestern) Nile river basin. While I don't have enough knowledge on the exact conditions that would allow or hinder such effort, I have found during my brief research some information that could be very useful for this particular scenario. First, there is a fairly dense network of tributaries around the white, blue and souther part of the main Nile river (though most of those around the white are within the Sudd) [Image 1 & 2]. If a state with enough capital could invest in irrigation and other ways to promote the deveopment of intensive agricultural practices, it may had been able to become a net exporter of agro produce. Second, a problem faced by the early Solomonids (starting 1270, but you might be able to make the Zagwe fall some decades earlier) was that while they achieved significant cultural development, urbanization remained underdeveloped, partially due to their lack of a permanent capital. And third, there are exactly 6 major cataracts in the Nile that delimitate its navigable sections, with the main one being, of course, the one that goes from lake Nasser to the delta [Image 3]. This means that if you want to support an invasion northwards and supply it by river, your supply line should begin in Nubia proper, which in my opinion is only feasable if you a)control that territory and b)you supplies get there in the first place by the Red Sea.
So that we know what we are talking about:
Image 2
Image 3
But military logical practicalities aside, getting a Christian state to amass that amount of power and territory while surrounded by islamic states is not going to be easy (though not impossible). I personally would have them expand south while avoiding conflict with the Somalians. The thing is that just having a large navy in the Red Sea when nobbody else does means that you have virtual control over all the transit that goes through it, which would automatically make every other state around you set on destroying you. So have them take as much of the decent agricutural land to the south and encroach around the Somalian coast, once they have built a decent powerbase, go north and conquer all of the blue Nile (the ideas for a road and a fortress are very good). What the Ethiopians have going for them is that their territory has pretty good defensive natural features. Because of the cataracts mentioned earlier, suplying an attack from egypt implies a lot of dessert marching, which is a logistical headache, whereas the coastal areas to the east are overwhelmingly mountanous terrain. So after managing to win a few defensive wars, building a sizable powerbase, and getting a souce of income (as discussed earlier), they should be ready to take the coastline and start building a navy that both puts them into contact with the east and allows them to project power into Yemen and further north of the Red Sea coast. It would probably be a good idea to get a foothold in Yemen, as by this point they already have the emnisty of Egypt, and during this period nobody else is really strong enough to matter. After that comes the takeover/vassalisation of Sudan/Nubya, because, as I already mentioned, the cataract on the north end of Lake Nasser marks the begining of the longest, most important, and most navigable tram of the Nile River. What it come down to is, in reality, Egypt is particularly vulnerable to attacks from the south, its just that IOTL there were no powerful states in Nubya during this period, but the Nubyan dinasty of antiquity and the Nubyan ocupation of Cairo to realease the Patriarch of alexandria from the sultan during the early islamic period (I think) did not come out of nowhere: its very easy to ship stuff downstream on one of the most navigable rivers of the world, the only chalenging part is getting those supplies from your powerbase to the final tram.