1) Yes its possible to fly back from a different place just that it might be easier to check with a travel agent to help book the tickets as it might be different company or more complicated than normal return flight.
But like I know Air Asia fly from/back from both Macau and Shenzhen so it should be possible to take Air Asia both ways. You tried their website?

2) I am not msian so it might be different. But from HK to Mainland you most probably need a different visa if you need one to enter HK, it's still considered different countries from visa/borders point of view.
From my knowledge of HK/Macau/Mainland visas, HK and Macau should be the same visa (if any), Mainland different one.
For msian I am not sure if you need to get the visa before flying for HK/Macau, for Mainland you definitely need it

Maybe other ppl can give you more details 

Msian for sure need Visa to China. You can apply from Bank of China/OSK building in Jln Ampang. Otherwise pay any tour agent to apply one for you.

Hong Kong & Macau is visa free for M'sia. No problem within these 2 cities.

Previously during Beijing olympic. VISA on arrival is not possibel now not sure but it is cheaper & safer to apply here in KL. You dunwan to be stuck hours waiting at the border