People in the Roman world discontinued using complete Roman names over a period of centuries in late antiquity and the early middle ages. By about 500 or 600 almost everyone would have just used their personal name, without any clan or family name.
I note that the eastern section of the Roman Empire continued for centuries after the western half fell, but Greek replaced Latin more and more. Aristocratic families there started using Greek surnames at least as early as before the year 900. I think that Emperor Romanus I Lekapenos (r. 920-44) was the first emperor to have a surname, and that he was the first in his family to use it.
Surnames developed more or less independently in western Europe. I have the impression that in rural villages tax collectors were responsible for surnames. Since several villagers would have the same personal name, the tax collectors wrote descriptors after the names in their list, descriptors which were used thoughout a person's life and eventually became hereditary.
Nobles in England began to use surnames in the middle ages. The first Scottish kings to have surnames were John Balliol (r.1292-96) and Robert I the Bruce (1306-29). I believe that Edward IV (r.1461-1483) was the first king of England to use Plantagent as his surname, and Henry VII Tudor was the first noble with a surname to become king of England. And even the present royal family doesn't have a real family name.
In larger towns and cities in western Europe, there would be many more men of the same personal name than in a village, so telling them apart was a bigger problem, and so surnames may have begun earlier than in villages, and used by aristocratic families.
Apparently all the Doges of Venice had surnames since 742. So apparently the use of surnames in the Italian language was common in Italian cities since quite early in the middle ages.
And during the Renaissance it became common for educated people to Latinize their names, which included surnames. So probably a lot of people adopted ancient Roman clan and family names.