You can also go with a Warlock who becomes a Paladin as Atonement for any evils they've done.
Also Paladin who is driven mad temperarily after seeing a Star Pact Patron in person and makes a pact in that madden state, yet later recovers with helped from love ones.
Then there is the possiblity that someone else makes a pact on your behalf. Ancestor X offers evil artifact to an Archdevil, but as part of the deal, Ancestor X and their descendants gain warlock powers. Basically Ancestor X prepayed for your pact, which given you don't have to give anything for, comes automatically into effect.
I also had an idea for an Aasimar where they make a Warlock Pact with they're Angellic Guide. Like maybe your guide has some kind of tie to a Fey God or is a Fey God, or your Guide has Fallen and become a fiend rescently and didn't tell you, until after tricking you into a pact, offers a seeker pact, or is a Divine Minion of... or is a Mortal that ascended into becoming an immortal Celestial while alive and offers you an Undying Pact, or you Angellic Guide got eaten by a powerful Aboleth who is pretending to your guide and tricks you into a Pact.