@ehBeth,
On continental Europe these 'travel documents' must have been in use earlier - for instance, in the 1470's, the city of Berne (Switzerland) issued about 50 of such 'passport letters' a day (actually during night, since that was done being at war).
Already in 1551 there was a "Reichspolizieverordnung" (police instructions for the
Roman Empire of German Nation) regulation the "passports".
There are notes by several travellers from the 14th/15th century what 'papers' they had to show where to get a 'free pass'.