I did a brief search at the US Patent and Trademark Registration Office. As far as I could tell, Paradox owns about 17 Conan related trademarks (not counting any that might be pending), including the name, likeness, etc. of Conan. Most of the nation names would be hard to trademark, as they're historical (the Greeks would likely object to someone trademarking "Argos" or "Corinthia", for example). "Hyboria" was trademarked, but "the Hyborian Age" wasn't, or at least it's not been approved yet.
As far as the stories go, you very well could release a new edition of REH's PD tales, but with Del Rey and others already beating you to the punch, why bother? But, because (in the US, at least) Paradox is recognized as the "heirs" of REH, writing new stories based on Conan, using identifiable parts of REH's IP without their permission, would probably be rejected outright by most publishers and land you in some legal troubles. IP law isn't about right or wrong, it's about who has the most money and can afford to bring legal cannons to bear. Defending an IP case in the US runs into the hundreds of thousands, or so I'm told (though IANAL).
Best,
Scott