There are many good answers, and I'd like to add St. Thomas Aquinas's natural theology to the mix, but the best answer is if we can find one from St. Paul himself. And we do. St. Paul goes on to speak of specifically how people are without excuse in the coming chapters. Jews by knowing the Law, sure, but even the virtuous pagans, who know what's right and still don't do it.
Romans 2:14, 15
2:1414 (Indeed, when Gentiles, who do not have the law, do by nature things required by the law, they are a law for themselves, even though they do not have the law. 1515 They show that the requirements of the law are written on their hearts, their consciences also bearing witness, and their thoughts sometimes accusing them and at other times even defending them.)
C S Lewis, mentioned in another answer, echoes this in the beginning of Mere Christianity. We know right from wrong; we argue about it; we make excuses, which shows we know it exists. He says that if God wanted to communicate His reality to us, He'd have to send us a message -- andmessage—and this, Lewis says, is that message.