| Sadurian |
The only way other than Ranger to get Favoured Terrain (another prerequisite for Nature Warden), is Barbarian True Primitive. That's not an option for Paladin, sadly.
RAW doesn't have Bond to the Land substitute for Favoured Terrain class feature, it just gives +2 AC in terrain chosen from the Favoured terrain list.
Bond to the Land:
Bond to the Land: Some gnomes have strong ties to specific kinds of terrain, as a holdover from their fey origins. These gnomes gain a +2 dodge bonus to AC when in a specific terrain type selected from the ranger list of favored terrains. This choice is made at character creation, and cannot be changed. This racial trait replaces defensive training and hatred.
It sounds like you are going to have to get very creative to make the leap from Paladin to Nature Warden.