Markos (Marco) is not a "real" Greek name.
Marco (the saint) was the Patron and protector of Venice. If you know Venice, the "Basilica di San Marco", the cathedral of Venice was build in his honour.
Off course, Venetians (almost Greeks) were present everywhere in Greece and the brought the name Markos with them.
Today, the name exists predominantly in Islands like Naxos, etc. In Turkey, you will find the name "Markoglou" (Markos's son) and in Greece the equivalent "Markopoulos", In Cyprus "Markou".
In Corfu ans surrounding islands you will find "Markatos", in Crete "Markakis", etc.
Markos should exist in Naxos and surrounding Islands. Start from there. The best way to proceed is to combine his and his wife's surname.