I think you should check El-Al (probably elal.com or elal.co.il), they may be operating direct flights Tel Aviv-Cairo on some days of the week. If they do, this is the most sensible solution, even if you don't find a direct connection on same day for Cairo-Marsa Alam, you won't get bored spending a day or two in Cairo.
All other solutions are either really expensive or incredibly tiresome and get you to destination exhausted. It does not look reasonable to travel from Tel Aviv to Eilat (bus/airplane), then to Sharm El Sheikh (bus? taxi?), then a ferry to Hurghada, then a bus further south? It is crazy... Or flying through Jordan (or Cyprus) making additional stop and connections will just sum too much time..
Caesarea, Scire, Achziv etc. are nice dives (IMHO Caesarea is boring) but extremely lousy when compared to the places you are looking forward to go- if you are time limited don't waste it on these sites.
Nothing to add. Just follow this advise !!!