What happens when there are two KoS Renly Baratheon cards in play during a melee? Are all Baratheon cards 2 less in cost around the board? We played it out as though they cancel one another as different Baratheon kings. As the text reads, "If Renly Baratheon is the only Baratheon king in play...". This has somkething to do with 'self-referential' rules, but I'm not sure on this one.

Yes. The self-referential nature of the text means that if an opponent has a Baratheon King character of the same name out, the play restrictions are no longer met and their text is not active.