Think about the real world
There are many conflicts in the real world, for many reasons. Look at news or a history book if you need inspiration. Not all of them are combat encounters, many might be detective work and exploration.
- Which church is allowed to tax/get the tenth in a village? Help the priests of Pelor against an attack by Asmodeus' children (insert $LOCAL_DEITY).
- Are there racial tensions between the races? Calm the mob of elves wanting to burn all halflings.
- Who illegally hunted a deer in the baron's forest? Free the arrested farmer or help prove his innocence so he won't be executed for his crime.
- A landslide destroyed the crop in the neighboring village, and they are running out of food. But giving them food from this village might lead to starvation in winter.
- A Party member is unfairly accused of theft. The punishment is cutting off the left hand. Fight the guards? Escape the guards (Skill challenge?) Prove innocence (How?)?
But much more important than the exact back story is in my eyes:
Make combat encounters diverse
It's not (only) the creature selection that makes an encounter interesting, but how you set up the battle. Let me make an example, with the same old 'bandit take village hostage' in three variations. I'm sure if you run it like that, the players won't complain it's always the same.
Devious, planning ba...ndits
The bandits have obviously heard of the wandering band of do-gooders and are prepared. First, they send in the dogs. Use skirmisher dogs that charge + make the enemy prone. Feel free to give them half HP or make some of them minions in order to make the battle shorter, but use enough different dogs they can't be locked down.
The dogs are backed by ranged attackers on the roofs behind chimneys - that means ranged attacks from cover, plus potentially combat advantage if they hid well. To get on the roofs, require at least a move action + athletics check. You can also make them minions, or at least some.
After two rounds, when the party is likely to be softened up, send in the Hog-Brothers, two large, burly fighters, brutes that will focus on the same target to make it go unconscious...
Trees are fun
Bandits have taken over the village, but the village is on a hill. When the party approaches, the bandits roll logs (trees) down the hills. That's a nice trap against Reflex that damages, secondary attack against Fortitude that slows. Once the party is up the hill, use charging brutes that push them down again. As always, use cleverly distributed archer minions to make it more dangerous.
Hostages
Again, bandits take over the village. Everyone is on the village square. When the party arrives, two bandits in the center threaten the peasants that were rounded up. Can the party lock down the two bandits and prevent an all-out slaughter, while fending off the other bandits? If you make the villagers run around frightened on the battlefield, you have another nice restriction: non-friendly area attacks kill peasants.
Build up a villain/villains
Don't worry too much about 'same backstory' for side encounters, it doesn't really matter as long as the fights are interesting. And you could build up a gang of bandits that terrorize the area... every session there's another gang-related side encounter. With time, the bandits also start hunting the party. This could tie diverse and interesting encounters together. Build one or two lieutenant for every side fight that has special capabilities (not magic, but either some leaderish/controllerish powers or a especially hard brute/soldier.
The rulings
My previous answer for this part was based on my reading on it. Crawford has talked, though.
If you spend 4 unbroken hours resting, for example, a DM could say that's one short rest.
and
After a short rest, the DM decides how much time must elapse or how much activity must occur before another short rest can start. Maybe 0 minutes, 1 minute, 10 minutes, or 1 hour. The key is that rests aren't meant to be a button you press. They're a narrative pause.
The first one would still be subject to "I can simply break the 4 hours by casting cantrips in the air for a few minutes", so it would not be 4 "unbroken" hours any more. The second statement is stronger though: it says you, oficially (i.e. not Rule 0), decide what counts as actually breaking a rest and starting another.
The World
Even if the rules don't prevent your fighter and warlock from short resting for many consecutive hours, there are lots of things preventing your scenario from happening in the adventure.
Where exactly are these characters? They can just stay still, unmoved, for three hours, and nothing happens? Why aren't they being swarmed by enemies?
That's how I usually deal (and how other DMs I've played with and have watched deal) with rests: you can take a short rest and then start moving before every enemy nearby decides to eat you. In your specific scenario (overworld, as mentioned in a comment): are they on the woods? Make a hoard of giant spiders notice them after one and a half hour. Are they in a plain field? Oh, what is that flying over there? Is it a Young Green Dragon looking for food near its lair? Make them feel uncomfortable staying still for hours in the same dangerous place.
Honestly, if they can just sit still and relax for 3 hours uninterrupted, they might as well just sleep and relax for 8 and make a long rest, then everyone, not only the fighter, is back to full health, spell slots and class features.
But this usually isn't the case. Remember, the world is alive (I've read this phrase often here, and I liked it), if they are wasting time resting every hour each 1 hour and 10 minutes, they are wasting time. Conflicts are happening and resolving and they are being left apart because they are singing around a firepit. Maybe they missed a quest. Maybe a friend has died.
The Final Word
If you really want to hard rule it, remember you are the DM. In the end, you decide everything, from how long a short rest is to how many times Second Wind can be used in a given time interval. The book is your tool, not your master. But my point is that even if you want to go RAW and RAW ends up allowing this "exploit", you can still prevent it from happening in a number of ways without any extra ruling. Solving it without hard ruling will make the players feel less frustrated (as you mentioned one player has already left because it felt unfair that he was restrained by this method) and it is actually intended, as the world is dangerous and you can't just sit and rest anywhere in a dangerous world.
Best Answer
I'm going to address this in two ways. The first is with the resting rules as presented in the PHB/Starter, and the second is to have a short chat about the alternative resting rules as laid out in the DMG.
First and foremost, we need to talk about how resting works in 5e. Short rests have a timeframe of 1 hour, and long rests have a timeframe of 8 hours. This means that in most scenarios you only want to take short rests in dungeons, and to do so sparingly. To some degree, this is the point of the time frames being this long, dungeons are designed to drain resources from PCs so that final battles in dungeons are meaningful, at least for some value of meaningful.
However, each party is going to have their own comfort level with how many resources are expended at certain points in the dungeon and how much rest their heroes need. How much trouble they have finding a safe spot to rest (or how effective their watches are if they do take a long rest) is up to you as the DM. I can tell you that the first group of players I ran through the starter was feeling mighty uncomfortable by the time they cleared out the second or third encounter, several PCs had nearly died and it seemed like a really good spot in the adventure to take a long rest. How you adjudicate this as a DM is sort of up to you. Long rests are not completely interrupted if a fight breaks out, so it's within your rights to let your PCs rest, but to spring an encounter on them while they are sleeping (though, if you plan to do this, it doesn't hurt to let them know either implicitly or explicitly, that resting here is not safe and may end up triggering an encounter over night). If you really don't want them resting in a certain spot, let them know, they see patrols, or traces of them that seem to pass regularly, or whatever.
That said, in many dungeons, there is no reason that you can't simply let yourself out into the wilderness to go have a nap. This is a possibility in the first cave in the starter set. A 15 minute hike into the woods should reveal a reasonable camp site that won't get discovered by the goblins.
Finally, there are alternative resting rules. They basically allow you to adjust the amount of time short and long rests take in order to defray certain costs. For instance the easiest one changes short rests to 5 minutes and long rests to an hour. This is probably to extreme for your game at this time, but, just the same, it doesn't hurt to modify the time frames to get the game you want to play (these are completely laid out in DMG 267-268).
So, basically, the advise that I'll give you is decide the style of game you want, decide how hurt you want your players to be, and dictate (with some input from them to be sure) how they should be resting based on the style of game you are playing. In the starter (And this is what I've done in my 5e games, including the starter), don't be too hard on your characters for wanting to take a rest, it's not hugely consequential, and they'll probably have more fun if their toys are all available for the rest of the session.