Some new information: According to the (not always completely reliable) Thomas Cook Overseas Timetable there are ferries from as well Sudan as Somalia to Jeddah in Saudi Arabia, but neither from Eritrea nor Djibouti, none to/from Yemen. But they seem NOT to be dedicated to muslim pilgrims only, that was the ferries between Pakistan an Saudi Arabia. On the other hand, you´ll hardly get a visa for Saudia Arabia anyway.