Any country is their own sovereign
There is no international law that demands any state to allow anyone free speech of all kinds. Remember that your rights end where the rights of others [incl. society] begin.
And in Germany, the right of the society is defined as being not subjected to the symbols of illegal organizations, especially ones that try to violate the liberal democratic basic order
Also, Germany is not alone in banning the sentence or the accompanying gesture. They are also illegal to various degrees in Austria, Switzerland, Slovakia, The Czech Republic, and Sweden. It also can be illegal in the US, if disturbing the peace.
The sentence is an identifier for a banned organization
The sentence is certainly illegal if spoken to express certain things. However, it is legal to be used for example in art (films) and is commonly found in lecture material, as one example of how the nazi party identified.
But how? People are often confused, but the rule is actually somewhat easy: If you display any symbol of a banned, unconstitutional organisation (under § 86a StGB) like any of the logos of the Nazi Party and spiritual successors (those with a red bar: banned!) or even the PKK, then you are acting in an illegal manner. And unless you have an exception to claim, the determination can be done entirely on a factual basis by looking at the circumstances. Indeed, the mens rea requirement is so minimal (because the law is written in a way that there is none needed!), that posting photos of a swastika tattoo can get you convicted for jailtime
However, I mentioned exceptions. Those are in § 86a StGB(3), pointing to $ 86(3)&(4) [eng]:
(3) Die Absätze 1 und 2 gelten nicht, wenn die Handlung der staatsbürgerlichen Aufklärung, der Abwehr verfassungswidriger Bestrebungen, der Kunst oder der Wissenschaft, der Forschung oder der Lehre, der Berichterstattung über Vorgänge des Zeitgeschehens oder der Geschichte oder ähnlichen Zwecken dient.
(4) Ist die Schuld gering, so kann das Gericht von einer Bestrafung nach dieser Vorschrift absehen.
(3) Subsection (1) [and (2)] does not apply if the propaganda material or the act serves civic information, to prevent unconstitutional activities, to promote the arts or science, research or teaching, reporting about current or historical events, or similar purposes.
(4) If the degree of guilt is minor, the court may dispense with imposing a penalty under this provision.
That is why we have swastikas in German school books, as those tell about the horrors of nazi germany. That is why the logos can be found in research material and history books analyzing the use of the symbols in different countries. That's why the news outlet filming the demo where people yell Heil Hitler show that footage without precautions (unlike those that fly the banned symbol!)
That is why you can have the film Inglorious Bastards with all its Swastikas and people yelling Heil Hitler, but its advertisement material was specifically altered to not show those.
However, until August 2018, computer games were not accepted as arts. This is why the German versions of Wolfenstein that did get a german release before had been altered to remove Swastikas and voice lines. But the "Sozialadäquanzklausel" had been applied to computer games in August 2018, and the games got (after some other hoops) re-released in their international version on 22nd November 2019.
How come some ideologies are banned?!
Germany's equivalent of a constitution is the Grundgesetz (Basic Law). Its first 20 articles (not paragraphs or sections!) prescribe the rights of any person. The very first and most important one is, and the very first sentence of it makes clear what the very guiding principle of all other laws has to be (emphasis mine) before any of the other basic rights are enumerated.
Art. 1: Die Würde des Menschen ist unantastbar. Sie zu achten und zu schützen ist Verpflichtung aller staatlichen Gewalt.
Art. 1: (1) Human dignity shall be inviolable. To respect and protect it shall be the duty of all state authority.
This is the most absolute right anyone can have. There is no provision in any way that would allow (or make it possible!) to strip or reduce the human dignity and every human being, living and dead, has it. Violations of human dignity have been used quite often to repeal laws, such as several incarceration methods or when cuts to the social security system would prevent someone to live a life that would be without dignity.
Human Dignity is the measure that can be used to cut all other rights. In fact, it is explicitly the foundational principle of all german laws, that rights are not granted beyond where other rights start and that nobody has any rights when it comes to harming the constitutional order derived from the Grundgesetz (emphasis mine):
Art. 2: (1) Jeder hat das Recht auf die freie Entfaltung seiner Persönlichkeit, soweit er nicht die Rechte anderer verletzt und nicht gegen die verfassungsmäßige Ordnung oder das Sittengesetz verstößt.
(1) Every person shall have the right to free development of his personality insofar as he does not violate the rights of others or offend against the constitutional order or the moral law.
Now, where comes freedom of speech? Only in Article 5, and it is absolutely not absolute but has defined limits (emphasis mine):
Art 5:(1) Jeder hat das Recht, seine Meinung in Wort, Schrift und Bild frei zu äußern und zu verbreiten und sich aus allgemein zugänglichen Quellen ungehindert zu unterrichten. Die Pressefreiheit und die Freiheit der Berichterstattung durch Rundfunk und Film werden gewährleistet. Eine Zensur findet nicht start.
(2) Diese Rechte finden ihre Schranken in den Vorschriften der allgemeinen Gesetze, den gesetzlichen Bestimmungen zum Schutze der Jugend und in dem Recht der persönlichen Ehre.
(3) Kunst und Wissenschaft, Forschung und Lehre sind frei. Die Freiheit der Lehre entbindet nicht von der Treue zur Verfassung.
Art 5: (1) Every person shall have the right freely to express and disseminate his opinions in speech, writing and pictures, and to inform himself without hindrance from generally accessible sources. Freedom of the press and freedom of reporting by means of broadcasts and films shall be guaranteed. There shall be no censorship.
(2) These rights shall find their limits in the provisions of general laws, in provisions for the protection of young persons, and in the right to personal honour.
(3) Arts and sciences, research and teaching shall be free. The freedom of teaching shall not release any person from allegiance to the constitution.
Parties and organisations that can't abide by the other rules of law because of their ideology will get banned based on that. In the case of the nazi ideology, it's quite simple: The core idea of Rassenlehre and its believe in Untermenschen is so deeply dehumanizing that there can't ever be a way to get that in line with the very first (as well as 2nd and 3rd) Article of the Grundgesetz. Or to quote the words of Amon:
Nazi ideology denies dignity to some humans, goes against the liberal-democratic order, and therefore cannot enjoy the usual protections. Rule of law is still maintained because restrictions to the freedom of expression are codified in law, and violators will get a fair trial.
You see, you simply don't even have an absolute right to disseminate your ramblings, because the Basic law itself points to the general laws that ban the dissemination of certain materials. This is how § 86 StGB can ban any propaganda material for organizations and § 86a StGB subsequently bans their symbols, including gestures and slogans.