The word "villain" is derived from the 14th-century word "villein" which means:
a free common villager or village peasant of any of the feudal classes lower in rank than the thane.
So originally, it would certainly have carried the connotation of low birth. I found this question on English Language & Usage about the process of how the word changed meaning which you may find interesting.
The question thus becomes when did the meaning change. As it so happens the Oxford English Dictionary provides various examples of its usage down the ages. And from this, we can see that the transformation of meaning into "scoundrel" happened before Shakespeare's time.
By far the most pertinent example is:
The greateste vyllany in a villayne is to be gyuen in largesse of lyes.
- Ld. Berners tr. A. de Guevara Golden Bk. M. Aurelius (1546)
There are various interpretations of this sentence which cannot be unpicked without context for the passage, which I cannot find. In all of them, however "vyllany" (i.e. villainy) has to be understood as a synonym for wicked behaviour. That, in turn, strongly suggests that "villayne" (i.e. villain) was, by 1546, understood as a synonym for one who was wicked.
Its actual meaning in the passage is unclear, and it could possibly still mean "serf". So while not definitive as regards Shakespeare's meaning, we can conclude that by his time, the modern meaning of "villain" was widely understood.
As regards this specific usage, then, it is worth noting that Claudius is not a serf but the opposite. He is a noble: the King's brother and, later, the King himself. There is nothing in the play to suggest we are to think this claim to nobility is invalid. Indeed, if it was, you might imagine Hamlet might have pursued it as a means to oust Claudius from the throne.
Finally, we can look at some other quotes in which Shakespeare uses the word villain, including another from Hamlet:
One may smile, and smile, and be a villain!
An evil soul producing holy witness Is like a villain with a smiling cheek.
This is the excellent foppery of the world, that when we are sick in fortune (often the surfeits of our own behaviour) we make guilty of our disasters the sun, the moon, and stars: as if we were villains on necessity;
And every tongue brings in a several tale, and every tale condemns me for a villain
In each of these cases, the context indicates we should read "villain" in the modern sense rather than to mean someone of low birth.