As a paladin, you may personally be lawful, but your cause, your quest, your goal, is Good. Being lawful is about honor and honesty and integrity; it is your means to an end—but the end goal is Good. That doesn’t necessarily mean that you should overthrow the lawfully-elected mayor of a town just because that mayor happens to glow under the effects of detect evil, but it does mean that you can work to prevent an evil ruler from doing evil unto their subjects—even if you have to break that ruler’s laws to do it.
On the other hand, there are any number of reasons why someone might glow under the effects of detect evil, that really may not justify you doing anything at all to them. For one thing, creatures with the evil subtype—which means they literally have evil baked into their bones—can yet still be redeemed and be good-aligned. Despite their alignment, they will still glow under the effects of detect evil,1 because no matter how good they act, there is still evil as part of their flesh and detect evil will see that. Such creatures will also glow under the effects of detect good—as they are good—but a paladin doesn’t have as easy access to that as they do to detect evil. Attacking a redeemed fiend or other evil-subtype creature for no other reason than that they glow under the effects of detect evil would almost-certainly be an evil act.
More pertinantly, being self-serving, callous, and greedy can, particularly when not mitigated by forms of generosity and assorted good, lead to an evil alignment. But these personal qualities don’t automatically make a person a bad leader of people. Mayor Vetinari of Discworld fame is a prime example, if you’re familiar. There are all kinds of self-serving reasons to not visit wanton cruelty upon your subjects—there can be very self-serving reasons for making their lives better. Particularly if the mayor is democratically-elected, it’s in their best interest to make people happy. It may not be a bad situation to have a certain type of evil character in charge.
So a paladin has to weigh all of that. They have to be responding to some actual evil done to others, innocents harmed and so on. They can’t just knock off the mayor because they don’t like their attitude, or don’t like how they look under detect evil. There are ways to be evil without deserving death (or injury or exile or humiliation), and the paladin has to be aware of that.
Thus, you are right to be hesitant. But you also should be decisive—if the mayor isn’t just evil because detect evil says so, or because they’re self-serving, but because they are actually harming innocent people, you as a paladin are empowered to act in order to serve the most Good. And there are honorable—lawful—ways to go about doing it, insisting on eliminating collateral damage, ensuring that any surrenders are honored, and so on.
Finally, while we’re on the subject, make sure you talk to your GM about all of this. Everything I’ve written here is supported by the books, but... people tend to have their own ideas for alignment, paladins especially, and alignment is vaguely-defined enough that they can rationalize those ideas against what the books say pretty well. Alignment is a really problematic part of the game, the cause of a lot of arguments and strife, primarily because the book authors can’t really define “good” or “evil”—everyone in the world has pretty dearly-held opinions on what those words mean—and definitely can’t adequately define “lawful” or “chaotic”—which are a tangled knot that are almost impossible to untie. So make sure you understand what your GM, in particular, believes about these words.
Most creatures that have this subtype also have evil alignments; however, if their alignments change, they still retain the subtype. Any effect that depends on alignment affects a creature with this subtype as if the creature has an evil alignment, no matter what its alignment actually is.