I just checked the information I had on AMKA on the Living in Crete main site, page http://www.livingincrete.net/natinsIKA.html
and I do in fact mention the health book, however this now appears to be wrong. The information was taken from the AMKA website when it came into being a number of years ago, but checking the AMKA website again now there is no mention of the health book. I suspect therefore this was the information given at the inception of AMKA and during the transition, when most Greeks and residents already had health books.
Basically the AMKA website http://www.amka.gr
now says you just need your passport (but they may also ask for another document showing your father and mother's names).
Any KEP office can issue the AMKA.