I doubt the Paladin will choose a new smite each level. For one, that would require there to be AT LEAST 31 smites to choose from, so that there'd be some actual choice involved. Realistically, you'd want about 60. I don't think the book will have 60 paladin smites.
There are a lot of other progressions that would match 1, 13, and 27. Every odd level would do it. Level 1 plus every 6 levels after it would get you 1, 7, 13, 20, 27. I'm sure there's more, plus there's "when we darn well say so" as an option.
I'd also be surprised if the only choosable paladin abilities were smites.
Regarding the in game explanation- Its a paladin. He's doing magic, except because he's a paladin, he doesn't wave his hands around like a little girl to do magic- he hits things in the face while channeling divine energies to enact his will. There, solved that one.
I like the idea of charisma modifying the paladin's special attacks. I like playing characters with spread out ability scores, and this suggests to me that a bunch of mid level numbers might be a good option for a paladin.
Regarding the use of low level smites at higher levels- If this is like other supplements, the way that will be handled is that you'll use your smite selections to drop a lower level smite and gain a higher one that does a similar effect, but better. Like with Renewing Smite. I'll bet there are other healing smites in the PHB, and the idea is that if your focus is on healing smites, you'll upgrade over time rather than continue using the original.
Binding Smite- That's... a pretty cool effect. Its tactical. I really like it. I'm kind of sorry its such a high level though.