I have used Lexol leather cleaner for a lot of years and have never had a problem with it for general cleaning. If you really want to strip all the wax off of your shoes (in the future) I would suggest RenoMat, which does not require a lot of rubbing. The chemicals in RenoMat also tend to pull some of the oils out of the leather as well, so you will want to add some leather conditioner to the shoes after using the RenoMat.
I would use Lexol leather cleaner when you want to clean your shoes and remove a few layers of wax (use before you polish the shoes for the fourth time in a row, or so). I would only strip all the way down to the finish every year or two (depending on how often you add polish to your shoes).
The damage done does not look too major, and you should be able to hid it with shoe polish. If you did in fact remove some of the factory finish, that area will tend to absorb water and oil a little more than the surrounding area, so it might darken more in that area when you apply polish, but will lighten back up as the oil soaks deeper and the excess is wiped off (and the water - if any- evaporates).
In regard to which polish is better to use to cover damage, either cream or paste work fine for slightly different reasons. Cream typically have a higher pigment ratio than paste, mainly due to the inverse wax ratio. When you polish your shoes with colored shoe polish you are just putting colored wax over the leather, the color does not go into the leather itself. Therefore the more wax you have the more color you have (think of trying to look through a number of lightly tinted windows stacked back to back). Cream polish makes up for this by using a higher pigment concentration in the mix, since it has a lower wax ratio.
I can also vouch for the effectiveness of RenoMat. Recently used it to strip down a pair of AEs that had some weird coloring going on on the toe box (probably my first attempt at burnishing). The RenoMat took it down to the bare leather and I was able to use Renovateur, cream and wax to make them look brand new.