"Sex stories" as you put them are usually extremely relevant to determing whether or not a politician behaves ethically. It is generally believed that people who do not act ethically in some parts of their lives will also act unethically in others, some of those being very relevant to the voting public.
"Sex stories" are also embarrassing and therefore create the opportunity for a politician to be blackmailed. Even though President Donald Trump has not had any "sex stories" while serving as the President, his prior behavior of cheating on his wife with a pornographic actress was embarrassing enough to him that he was willing to pay that actress money not to talk about their affair. Other politicians who are not personally wealthy and therefore cannot afford to pay blackmail may choose to make problems like that go away by using the powers of their office in ways that they would not ordinarily be used to benefit the blackmailer at the expense of the public.
It is also often not the case that "sex stories" are totally private matters; many of them involve the behavior of politicians in their work environment with people they work with at times when they are supposed to be working. A recent notable case in the United States is former Representative Katie Hill, who recently resigned from Congress because it was discovered that she was having a sexual relationship with an employee of a congressional committee, which is a violation of House ethics rules and would likely also meet the legal standard for workplace sexual harassment if it occurred at an employer who was not Congress.
It is also not unusual for politicians who are engaged in clandestine sexual affairs to commit crimes in order to cover them up. Former President Bill Clinton lied under oath about his affair with Monica Lewinsky during grand jury testimony; perjury is considered a felony under federal law that is punishable by a 5 year prison sentence. Clinton was not indicted for this only because he was the sitting President; the President cannot be indicted according to longstanding legal opinion. So, the House of Representatives impeached him but the Senate refused to remove him from office.
So yeah, if the "sex stories" were merely about consenting adults having sex with their spouse's knowledge and consent, they wouldn't be much of a big deal. They usually involve crimes or abuse of their offices in one way or another, so aren't merely "personal."