To search for trademarks, use usethe website of the united states patentUnited States Patent and trademark officeTrademark Office. But you can assume that the name of every major comic book character and villain is trademarked. Corporations like Marvel and DC which make vast amounts of money by licensing their intellectual property are very thorough in this regard.
Having almost the same name can already be an infringement when there is reason to believe someone might mistake your character for the trademarked one. I am not a lawyer, so I can not give you an estimate how likely it would be to get away with either of your examples when in court, but the chance is high that you couldn't afford to defend against a lawsuit to find out, so you should better avoid it.