If you want a slightly less magical paladin, with a bit of a nerf just have all paladins use the Warrior of holy light archetype. They trade all of their spell-casting for some effects that are useful, but not nearly as useful as spells.
Its not the spellcasting I'm worried about, its all of the abilities.
If you're that worried about paladins being too powerful, just disallow them and reflavor fighters into holy warriors. There you go.
We really need more info before anyone can make specific suggestions.
What classes are allowed and how have you changed them?
How common are truly evil foes?
How restricting would a paladin's Lawful Good requirement be there?
There are probably many more important questions but today I'm too stupid to think of them so these will have to do for a start.
Its not the spellcasting I'm worried about, its all of the abilities.
What specifically are you worried about here? That a pally in a low magic world is going to be unbalanced because they are a pally, or because of all their 'magic' they are going to break the 'theme' of the world?
If your worried about balance, are you changing any other classes core abilities as well? If you are.... best of luck to you. I hope the game balance works out OK, but there is little advice I can give you. I haven't done the maths on low magic worlds and how they affect what classes and what becomes OP vs not.
If your not doing rebalance on the other classes, then I'd stay away from doing it here. If your after something less 'magical' then have a look at the Cavalier and Samurai class (strip out the Knight and Japanese themeing if you want and re-skin it), but if your worried about pallys breaking the theme of the world, then just have them as 'NPC only'. Resign pallys to being a 'prestige' class in your world. These ARE now your rare holy knights that a 'True' paladin might be the captain of the guard at a large temple... not every single guard on duty there.
The other alternative is to re-skin some other things about the class and keep the mechanics the same. Have them as faithful warriors, but they are sustained by their own faith, not the gods empowering them. Their devotion and drive is what sets a pally apart from a mere fighter, NOT the gods.
- Change hitpoint damage to fatigue, tiredness, poor morale and 'luck' and LoH and Channel becomes inspiring speeches.
- Detect evil becomes training in identifying a jotun's blood in a person or alike. Alternately, just a 'sixth sense' of if you pay attention to him carefully, you can get a feel for what sort of a person he is (queues similar to high sense motive)
- Grace.... low magic means this shouldn't come up as much, but could be runic wards and alike, or just 'Yeah... we train them to be tough as nails'. Similarly with divine health. Same with Aura of Resolve.
- Aura of courage... Again, nothing more than inspiring leadership to others, and refusing to break that example to the pally himself.
- Smite evil, re-skin cosmetically as something similar to the Cav / Samurai challenge, but leave otherwise as is.
- Divine weapon bond becomes tricky in low magic because it's designed and scales for a 'normal' magic world. You might have issues with the balance there if at 8th he can take his +1 sword (uber rare in low magic).... and make it a keen, flaming +1 sword... Again, if it's just a reskin your after, have him throw wildfi.... I mean Alchemist's fire on the blade. Once you've got this power anyway though, your into caster territory for a pally anyway. You could leave this as is as a specialised 'summon' spell for pallys.
Flavor wise have you considered linking paladins to Valkyries instead of gods? As you don't have clerics servants of specific gods seems to be somewhat against your theme and the abilities match up quite well.
Ability wise if you have not rebalanced the other classes and there are not that many big supernatural enemies paladins should be fine as is.
In a couple hours the Warpriest playtest will come out, might be worth looking at for ideas on what to do differently with the class.
So opinions on what I should call the samurai reskin?
Yee fripping GODS I could have some fun with an order founded around that in a high magic world...
I don’t think you need to do anything if you keep the paladin. Taking away a class ability without giving something in return is unfair unless this is being done to all classes. As to the paladin being overpowered because of his abilities I also don’t think this is going to be a problem. Most of a paladins abilities are designed to help him against things that are probably not going to be all that common. Smite evil is completely useless if the opponent is not in fact evil. Detect evil only works on characters over 5th level. Divine grace is not that important in a low magic campaign because there are less spell casters to cast spells on him. Looking over the rest of the abilities they also become less relevant in a low magic campaign.
From what you have posted you would probably just be better off not allowing paladins. They really do not fit the campaign that well anyways. You are looking at changing so many aspects of the class that it is no longer a paladin. If I sat down to play a paladin and was told that all my class abilities had be removed or changed I would be a bit upset. Since you do not have clerics, but do have druids a ranger would be the logical choice for a divine warrior. Also a barbarians rage could be considered a god granted ability and they could fill the role of divine warrior.
I asume it is the weapon and Mount thing you consider charging. If no body else gets a magic weapon that should be ok. But when you go low magic remember that it is the non magic classes that suffer. So going low magic but allowing Spell casters will often resultat in all caster groups.