Not easy but via JNB is probably best (fly the longest on a quality Star Alliance airline (ie LH). Even if flights aren't operating to Madagascar, you can still have a good time in S. Africa.
There are very few flights but Inter Air does service (weekly?) TNR (Antanarivo) from JNB. You may also be able to connect via Reunion or Mauritius once a week.
Air France does fly several times a week from CDG direct to TNR which, unfortunately, is the best routing (but not a Star carrier

). AF actually has one of the best Europe to Africa networks.