Budget per day and person in EUR, backpacking, cheap hotels and hostels with roadside meals:
Turkey 35-40
Syria 15-20
Jordan 25 (keep an eye on the entry fees for Petra, they can blast your budget through the roof)
Egypt 15-25
Don't know about Libanon, but price levels should be somewhat close to Turkey, maybe a bit less. Turkish Cyprus should be the same as Turkey, Greek Cyprus should be the same as Greece, 50 EUR per day.
BTW, concerning the flight out of Cairo and the flight to Turkey: As a Malaysian you can enter the Schengen Area visa-free, I would thus check for cheap flights from Cairo to Europe and from Europe to Turkey. I've seen flights from Berlin in Germany to Istanbul for 70 EUR and from Cairo to Germany for 20 EUR.
See www.skyscanner.net
Flights Singapore-Frankfurt might also be cheaper than Singapore-Istanbul.
If that does not work for you, Cairo-Istanbul should be somewhere around 200 EUR return.
Personal favourites to add to the list:
Philae Island
http://looklex.com/egypt/philae.htm
If you go on a tour to Abu Simbel from Aswan book the long tour, it will include a visit to Philae Island. The price for the tour should be somewhere around 15 USD.
And although I haven't been, there are some raving reports from Dahab, mainly for hanging out, diving and relaxing.
And if you are really into Muslim culture, arts and architecture you should check out the desert castles in Jordan. Most people only go to see Petra, Wadi Rum and maybe the Dead Sea, so they are a bit of an insider's tip, but worth it if you are into these things.
http://www.saudiaramcoworld.com/issue/196303/jordan.s.desert.castles.htm
http://www.atlastours.net/jordan/desertcastles.html
http://www.kinghussein.gov.jo/tourism.html
One more tip: Check out the visa situation on Egypt, I think you need to get a visa in advance for Egypt if you enter via the Sinai (ferry from Aqaba to Nuweiba).