Welcome back to the Wefugees Community and thank you for reaching out to us again.
I am afraid that in case of subsidiary protection, obtaining the visa for family reunification for people who get/got married after the initial flight (leaving the country of origin) is only granted in very exceptional cases. I am sorry that I can not give you more positive information here. But since I am also not very familiar with similar situations, I will link our dear expert @Alla_fka here. I hope that she can add more details or correct me, if necessary. Furthermore, I would recommend that your fiancé is seeking individual advice in a counselling office or from a lawyer as well in order to assess whether an appeal against the decision (and eventually obtain the refugee recognition) could have good prospects. Please note that the period for filing an action is most probably only 2 weeks!
However, I just checked the website of the German embassy in Malaysia and learned that Malaysian citizens do not need a visa for the so-called Schengen-area. Here it says:
Malaysian citizens do not require a visa when travelling to one or more of the Schengen countries for business or tourism purposes. The stay in the Schengen States, however, may not exceed 90 days within a 180-days period. This means that once you have stayed for 90 days in any of the Schengen States, there will be a waiting period of 90 days imposed before you can re-enter any Schengen State.
Please note that the Malaysian visitor will need to present a valid Malaysian passport, proof of sufficient funds and a return airline ticket upon arrival at the first point of entry in the Schengen States.
For the requirements of the permanent residence permit ("Niederlassungserlaubnis") you may see this website, for instance. In general, people possessing a temporary residence permit for a minimum of five years can apply for the permanent one.
I hope this information are useful to you and don't hesitate to get back to us with any further questions.
All the best,