The spud gun uses air pressure to shoot a projectile - unusually a potato - at high speed towards a distant target much similar to todays revolvers. The only difference is that there is no gunpowder. Can people in the medieval age as early as 5th century A.D. develop a potato gun that kills? The projectile can be anything but I'll applaud the gunmen who can shoot lethal potatoes.
The oldest known air gun dates back to 1580. A 5th century weaponsmith faces great challenges in creating a similar weapon. The primary problems will be in creating a hand-held weapon able to withstand the pressures involved and with the necessary seals to avoid significant leakage. Did they have the knowledge, and even if they did, did they have the materials?
There's two types of air guns, spring and pneumatic. Spring piston guns use a cocked spring to drive a piston to generate the pressure to fire the round. They have the advantage of not needing a sealed, pressurized reservoir. Their disadvantage is in the time and force necessary to recock the spring and the complexity of the piston and pressure chamber.
In the 5th century, making reliable, compact and powerful springs would be very difficult. Compact and reliable coiled springs were not introduced until the 15th century. Even with the knowledge of coiled springs, steel making in the 5th century was in its infancy and would not be up to making spring steel up to the task.
Sorry, no springs in the 5th century.
In addition, while storing compressed air was not necessary, the chamber would need to withstand the extremely high pressure and heat produced by the piston. I do not believe 5th century metallurgy was up to the task.
The other type of air gun uses a pressurized reservoir of compressed air. This introduces big problems of how to manufacture a compact, man-portable vessel to withstand the pressure and control leakage. This problem was solved in 1780 with the Girardoni Air Rifle adopted by the Austrian Army. Watching that video will give you an idea of what is involved in making a successful air gun.
The primary problems are the reservoir, seals and valves. The strength and fine metal work of a threaded valve is likely beyond 5th century metallurgy, not to mention the small holes and pins, though it could be possible with very careful brass work. The seals available would be things such as leather, wax, and if they're very lucky, natural rubber. As we'll see in a moment, it's not likely they'll stand up to the pressures.
In the video, they estimate the pressure in the Girardoni reservoir to be 800psi or about 55 atmospheres. This is a lot. It's the pressure at 550m underwater, four times the test depth of a WWII submarine. A locomotive engine was considered "high pressure" if it used 350psi and those were not worked out until the 1800s. The Girardoni reservoir was designed to fire multiple rounds, a single shot weapon could get away with less pressure and a smaller reservoir, but I don't believe the reduction in pressure would be enough for 5th century technology. It would be nice if someone did the math. I sure wouldn't want to haul one around the battlefield knowing it might blow up.
So no, a 5th century weaponsmith could not create a reservoir able to hold a high enough pressure to drive a heavy enough ball at lethal speed.
No springs, no valves, no seals, no reservoir. It's not going to work.
Maybe @Vincent has the right idea...
Late answer, but another possibility... The kind of spud guns I've seen around here didn't use compressed air, but instead used a flammable liquid/gas like alcolhol or aerosol hairspray to propel the potato.
Granted, hairspray is not going to be an option, but high proof alcohol vapors are explosive too.
Basically any kind of fuel air explosion could propel the potato without needing a pressure vessel or springs.
Just because this is a fun video, an explosion in a potato gun at 20,000 fps
You could probably conjure something up with the right medieval tools and resources. Although smelting and molding iron was still a new concept, parts could technically be made, and with the right organic binding agent, you could make a reliable pump based air cannon. But, if your going to be shooting potatoes, you better make sure your not Irish or Latvian.) ;)