Yes, Rechtsstaatlichkeit only means that the state and its organs have to follow the law themselves. It doesn't say anything about the moral quality of the laws.
The Nazi state had to follow its own laws. They just had such laws that enabled the total lunacy that the 3rd Reich was.
All I'm saying is: If you decouple laws from morality you get a really bad time.
You are absolutely right saying that rule of law is not sufficient condition for the existence of modern society. It was a bit confusing still, because nobody claimed the opposite: the comment you replied to was saying rule of law is a necessity.
> The Nazi state had to follow its own laws. They just had such laws that enabled the total lunacy that the 3rd Reich was.
This is false. Even if you take the Nazi propaganda that their laws were themselves lawful (which they were not, beginning with the clearly unlawful capture of power) at face value, the Nazi regime did not adhere to its own laws and regulations. While in some cases the Nazi regime did codify a basis in law for their atrocities (i.e. excluding and expropriating jews), much of the Nazi terror both in a civil and military context would have been explicitly illegal under the law at the time.
This includes the November Progroms of 1938 (https://de.wikipedia.org/wiki/Novemberpogrome_1938), large parts of the Nazi's approach to warfare, as well as the entire Holocaust (the murder of more than 6 million jews and other "undesirables"), for which the Nazis did not bother to create any legal justification.
While the Nazi regime was deeply bureaucratic (in that it documented its policies, orders and their results in high detail) this is not the same as "following the law". Most of the Nazi's atrocities evolved not through a process of lawmaking, but from their racist ideology and were given legitimacy through the highly personalized nature of the regime: Hitler was explicitly above the law, as were his orders, not matter if expressed through him personally or in his name by his followers.