I don't recall any direct REH gladiatorial references. I would say, however, that large, public arenas with gladiatorial combat and circuses and such would be fairly limited. Private arenas of the very wealthy would be more common, with "pit-fighting," as in the movies, predominating in semi-civilized areas.
Asgard, Vanaheim, Cimmeria would not have either arenas or pit fighting, save in the most "advanced" semi-civilized towns (and perhaps along the borders in Cimmeria). The northern barbarians would simply pick fights in the open streets with people who offend them (like in the movie "The 13th Warrior") and that would provide more than enough blood to slake even abarbarian's thirst. The Picts reserve all such "blood sports" for the realm of religious ceremony, with victims either being eaten by or switching minds with animals from the vast wilderness.
The semi-civilized Hyperboreans might have some small stone arenas, for gatherings, entertainment, and punishment, but not vast colosseums. Their "games" would probably consist of feeding criminals to polar bears or winter wolves. The border kingdom probably has a few wooden arenas (large pits, really) as it seems an area where blood sports might be popular.
Arena combat is not a very Mitraic kind of thing, so I wouldn't see any large public ones in Aquilonia, nor in Nemedia or Ophir, the strongest Mitra states. These states have theatres, large stone ones that rival those of Rome. Certain depraved nobles also may well have built their own small arenas, for their own terrible entertainments or for secret punishment of enemies.
I would say Zingara certainly has arenas, though they would be used more often for bull fighting and such animal entertainments than for human battles.
Brythunia probably has pit fights (as in the movies), being semi-civilizeed enough to have such.
The real arena battles would indeed be found in the middle lands, where Mitra worship is wekest (or non-existent) and the terrible southern magics and religions do not hold sway. Argos, Shem, Koth, and Corinthia would have full-scale arenas and gladiatorial traditions. The culture would be strongest in Koth, then Shem, then Corinthia, then Argos (which would also follow Zingaran traditions). In an earlier D&D Hyborian campaign (set during the time of Conan II) I had the largest arena in the world placed in Khorshemish, recently built by a successor to Strabonius; it was known as the "Strabonium." Arena battles in Koth and Shem are flashy affairs, veritable circus orgies of blood and death, while those in Corinthia and Argos are more business-like. In Corinthia the games are run by each independent city, and the gladiators fight for their city-state, while in Argos all gladiators are free men fighting for money and fame. In Koth and Shem it is a mix, and includes slave gladiators, recreations of battles, mass slayings of heretics by lions, and even the massivs "sea battles," which are hideously expensive in Shem.
Some of the eastern Shemite cities have arenas, including Zamboula, but the tradition is weak and the entertainment not as bloodthirsty.
Stygia and the Black Kingdoms lack arenas, as such public festivals are rare in those lands. In Stygia it is so because the needs of the people do not cross the minds of the rulers; you obey or you die, and because of the inculcation of the Cult of Set, most of them follow willingly. In the Black Kingdoms the situation is much like that of the Picts to the north; blood sport entertainment is reserved for specific religious festivals, and settlements do not get large enough to necessitate an arena or even a pit; victims are enver given a fair chance to fight back, after all.
The idea of gladiatorial combat has not really sunk in to the Turanian mindset, save amongst the most knowledgeable and depraved nobles, who might have their own small arenas.
Kosala has blood sports, of a sort, though this consists of a master strangler publicly strangling a sacrifice, prisoner of war, or criminal. Of course, the stranglers were from Yota-Pong, so the other cities of Kosala might well have other methods of execution, including traditional blood sports, or even something weird, say, nude sacrificial victims are each given a cat 'o nine tails or scourge and must fight each other in an arena, with the last man standing given his freedom. That would be quite a bloody spectacle...
Though historical India had arenas of sorts, I doubt such is found regularly in Vendhya. Perhaps the Kshatriya have some sort of formalized dueling system that could be considered a public spectacle. Or maybe one of the more vile gods of that land (Hyborian Kali, for example) have blood pits where victims battle for the honor of being slain mercifully.
Hyrkanians are not into blood sports. They don't need them. They slaughter entire cities during war, so blood sports are considered a bit too sedate and civilized. The various independent semi-civilized city-states of the Hyrkanian Coast, though, probably have pit fighting at the least, if not full-blown arenas. Being a strange mix of cultures, and semi-savage in character, blood sports are sure to be a popular entertainment.
Khitai and Kamuja are a bit of a mystery. Khitai is huge, with many different cultures, so anything is possible.