Because we couldn't enter Egypt without Carnets, we shipped two bikes from Port Sudan to Aqaba (Jordan) last December ........absolute nightmare dealing with the shipping agent in Port Sudan. If you choose this route, you are required to use a customs agent on both sides (Sudan and Jordan). I will never do it again....i'd sooner strap my bike to my back and swim across the Red Sea.
Because you're not on a bike, you have a better option. There is a ferry that runs from Suakin (About 30kms south of Port Sudan) to Jeddah, Saudi Arabia. You can get visas at the Saudi embasy in Khartoum without any problems. Just be warned though that the embasy is only open for a very short time in the mornings (not Fridays) and it is a shoving competition. There are immigration agents working the crowds, but when we were there, everybody who used them complained .......best to do it yourself.