Team Martial is very unique, but they shouldn't have problem with most encounters of the same challenge rating. Let me address your major concerns first and wrap it up with some other thoughts.
Not having enough magic
Lets break it down into two categories: damage and utility.
Damage - magic provides easy access to area damage, and different types of damage (e.g. fire, lightning, acid, etc...). Unlike rogues and barbarians, paladins and rangers have access to multi-target damage as well as other damage types. This will help you immensely when dealing with mobs of weak monsters, as well as monsters who are resistant (or worse, immune) to piercing, bludgeoning, and slashing damage. But hey, you'll have an easy time against anti-caster encounters.
Utility - magic provides some form of manipulation that is hard to do otherwise. By having magic, you may have easy access to more variety of skills that helps you deal with situations (e.g. being invisible, reading minds, mage hand). This is definitely something you can't make up for easily. There's often more than one way of solving a problem though, and it may actually be more fun now you have to think outside of the box.
Damage in close quarters
Paladin functions well in close quarters, and rangers are actually one of the more versatile ranged characters that can survive well in close quarters. A lot of the ranger's skills are melee combat side (e.g. being able to use melee weapon effectively). In addition, they have pretty decent armor and hp, compared to other ranged classes.
Stealth
There aren't a lot spells that can add to stealth aside from the invisibility spell. Besides, ranger's primary attribute is dex, which means the majority of your party is actually pretty stealthy.
Other thoughts
One thing you didn't mention is primary attributes. Team martial has only strength/charisma and dexterity/wisdom as the primary and secondary attribute. This will make intelligence checks quite difficult.
Finally, in D&D there are endless possibilities to approaching an encounter. While your party does not wield much magic, it doesn't mean you won't acquire access to it using other means. There are people with magic that may assist you. There are magical weapons and objects. No matter how you pick your classes and skills, no three characters party can cover all grounds. Team Martial looks like an interesting choice, and if I may dare say, the character classes your players want to play. I bet it will have many epic adventures and tales.
