Hello! This is a great question, and one that is highly debated in existing scholarship; Benedict Anderson, Eric Hobsbawm, and Ernest Gellner are the 'big three' academics who worked on questions regarding national identity, and all three saw nationalism as quintessentially modern, and therefore functionally nonexistent before the nineteenth century. All three used the term 'nationalism,' though there's quite a bit of difference between politically engaged nationalism and a vaguer sense of national sentiment. As the idea of 'sentiment' or feeling part of a nation seems to be more along the lines of your question, that's what I'll run with. I'll also focus on the case of England, as that's my main area of research (Welsh, Scottish, Irish, and British identity are entirely different kettles of fish!).

So if we're using the concept of 'national sentiment,' ideas about belonging to a broader nation go back very, very far. Borrowing your time frame of medieval history (c. 500 - c. 1450), we can discern evidence of people feeling themselves to be part of a 'nation' based on similar language and customs almost from the beginning. The Venerable Bede, for example, wrote The History of the English People in the early 700s, long before there was anything like a territorially united English kingdom. Though Bede showed partiality to his own small Anglo-Saxon kingdom of Northumbria, he still recognised a common ancestry, religion, and language among the various other Anglo-Saxon polities around the island of Britain. Bede's view of national sentiment is less tied to geography than modern conceptions might be, but it's still based in his own experience of essential commonalities between people, or groups of people, inhabiting a particular area.

Bede, however, was a Benedictine monk and therefore would have been far better educated and well-off than the majority of his fellow 'English people,' who probably would not have had access to the same historical or literary sources as Bede and his fellow monks. For most people, at least in England, national sentiment becomes much, much stronger during the course of the Hundred Years' War with France, thanks to a concerted effort from elites to boost morale among the common people who would have comprised the bulk of the soldiers shipped off to France. Such sentiments crystallised, in particular, around Henry V and his victory at Agincourt in 1415 (though it should be noted that a similar process worked among French troops with the figure of Joan of Arc and the Siege of Orleans in 1428).

Fast forward about a hundred years and you see England in the throes of the Protestant Reformation, with fierce debate between Catholics and Protestants over which was and ought to be the 'true' faith of the English people. Polemicists and theologians of all religious persuasions looked to English history (often using the Venerable Bede as a source!) to prove claims that their own faith descended directly from some kind of indigenous English Christianity and could thus be considered the one, true faith. By the quirks of Tudor genetics and the succession of Elizabeth I in 1558, English Catholics largely lost that particular battle, though some would continue to advance their claims of well into the seventeenth century.

The 'success' of Protestantism added another dimension to the ever-growing sense of English national sentiment. Much as had been the case with the French during the Hundred Years' War, the spectre of Catholicism gave English national identity an enemy to define itself against. Religiously-coloured events like the failed invasion of the Spanish Armada in 1588 only further strengthened English identity in this way.

By the time of Elizabeth I's death in 1603, a sense of 'Englishness' had permeated all levels of society, in almost all parts of the country. Religious tracts (like John Foxe's Acts and Monuments aka the Book of Martyrs), plays (Shakespeare's Henry V), and numerous popular ballads all spoke to the idea of a common English identity, drawing on the past century and a half of developments which had solidified national sentiment in the minds of ordinary people.

So in sum, if we're looking at the case of England, there has always been a sense of belonging to communities which are or at least resemble nations. But mass buy-in to that idea becomes most apparent around the beginning of the fifteenth century, and could pretty well said to be dominant by the beginning of the seventeenth century. Hope this is helpful!