自分の経験 10年以上前ですが、有料で預けることが出来ました。 さすがに10年じゃあてにならない情報なので、ちょっと調べたら、 旅行代理店は預かってくれますよ。 ハブ的な位置付けのパロスでは乗り換えの人が多くいるので、料金もそれほど高くないでしょう。 たとえば http://traveltoparos.gr/en/luggage/ パロスからミコノスの船のチケットを、パロスの代理店で購入する(あるいは引き取る)のであれば、 無料で預かってくれるはずです。
ありがとうございました。 早速のご返答ありがとうございます。これで安心してパロス島に行けます。