Wir können ja mal sammeln:
Ich kenne die Direkt-Verbindungen
Frankfurt - Vilnius (ab 89 €, d.h. knapp 100 € für Hin- u. Rückflug)
Hahn - Kaunas ("Billigflieger", je nach Buchung, Flüge um Mitternacht)
und bin schonmal
Frankfurt-Kopenhagen Kopenhagen-Palanga geflogen

(das ist sicherlich die teuerste Variante, aber dafür hat man die Chance, am gleichen Abend noch in Nida anzukommen

Wer kennt noch andere (Direkt-)Verbindungen bzw. kann sie kurz charakterisieren...??