Ich würde hier nicht mit Profiling ansetzen, um irgendwo ein paar Takte zu sparen, sondern an dem Algorithmus an sich ...
Wenn ich nicht komplett danebenliege, würde ich an der (ziemlich teuren) RotateList-Funktion ansetzen - die kann doch so ziemlich ersatzlos weg!
Diese Rotation um den StartIndex wird doch nur benutzt, damit du in der Schleife ListA[i] mit ListB[i] vergleichen kannst. Warum lässt du das nicht weg, und vergleichst ListA[i] mit ListB[(StartIdx + i) mod ListB.Count]? Dann ersparst du dir sämtliches Umkopieren der Listen (nach dem "Aufräumen"), und dein Algorithmus dürfte um ein Vielfaches schneller werden, da du damit einen Faktor von O(n^2) aus der Laufzeit rausnimmst (solange dauert das Rotate nämlich im Mittel!)
Dazu musst du ggf. die beiden Polygondarstellungen auf "offen" normieren (dazu hats du ja die passenden Funktionen), damit Start/Endpunkt auf keinen Fall doppelt vorkommen.
Interessant wird da höchstens noch der Fall, wenn du Kantenzüge zulässt, die sich selbst kreuzen, und somit ggf. eine Koordinate mehr als einmal auftauchen darf. Aber dann wird das Problem ohnehin schwieriger, weil du an diesen Kreuzungen ggf. anders "abbiegen" kannst, was letztlich auf Graphisomorphie rausläuft. Und das ist dann so schwierig, dass man nichteinmal weiß, ob es NP-vollständig ist oder nicht.
(Wobei es für den Spezialfall "Graphen mit Eulerweg" auch eventuell effiziente Tests geben könnte, da bin ich jetzt aber überfragt).