A Certificate of Airworthiness is an internationally recognised document, confirming basically that the aircraft complies with a certificated design (i.e. one with a type certificate and data sheet). The design standards are agreed by ICAO and implemented, with slight variations, by each airworthiness authority.
Several aircraft either are not type certificated (ex-military, amateur built, historic etc) and so cannot be issued with a CofA. A national authority, however, can authorise those aircraft to fly in their own national airspace with a permit to fly - usually with a requirement to demonstrate that they are airworthy and have satisfactory characteristics.
A permit to fly is not internationally recognised, so requires separate authorisation to fly abroad from the appropriate authority. In the case of amateur built in Europe there is an agreement that allows a degree of mutual recognition (ECAC 1980, I believe).