Gepäckaufbewahrung am Fluchthafen weiß ich nicht, es gibt eine, aber kA, wie die dort wirtschaften: einfach anrufen.
Welche Jahreszeit? Bis 22:00 in ein Hotel zu gehen ist nun wirklich nirgendwo ein Problem. Der Fluchthafen ist nur wenig außerhalb der Stadt und es gibt jede Menge Hotels und Unterkünfte aller Klassen. Mit ein paar guten Worten und dem Angebot, bei Abreise wieder eine Nacht zu bleiben, nimmt das Hotel wahrscheinlich auch die Radkoffen in seine Obhut.
Ich würde bei booking.com die Daten eingeben und irgendein Hotel auf der Karte anzeigen lassen. Da erscheinen dann auch alle übrigen und du kannst dich orientieren. Achja: nicht verunsichern lassen, von den Angaben von wegen "nur noch 1 Zimmer!" oder son Quatsch. Buch mal ein Hotel im Frühjahr 2019 in Wanne-Eickel, auch dort wird nur noch wenig frei sein....

Mit CP kenne ich mich nicht aus. Viel Spaß! Bin zw 16.6. und 22.6. auch auf Kreta.