Here's how I would handle this, if it were my story to write. Just brainstorming here!
As a side note: I wouldn't necessarily be so sure the young maidens would be the first to be sacrificed. Medieval times, even fantasy times, the infant death rate and death rate in childbirth were both pretty high. Between malnourishment, accident and disease, anyone capable of getting pregnant pretty much had to do it as often as possible, just to keep up with population replacement. Whereas, young men might end up getting conscripted by local mobility to go off and fight a war. It was a tightrope between having enough hands to do all the manual labor required to keep a subsistence economy going, versus a whole lot of people starving if the weather didn't cooperate and the crops had a bad year.
I'm assuming that the shadow striders can't, or won't, leave the vicinity of their hive for long periods of time (say, months or longer). If they could, all they'd have to do is hire out worker / soldier brigades as mercenaries. With the stipulation that they get to keep any prisoners they take, to bring home with them. A whole lot of nobles would absolutely take that deal. Particularly if the insect mercenaries fought alongside allied human wizards who could magically shield them from fire.
But that's not the route they want to go! Maybe being outside the Queen's telepathy range causes them to fall into a coma, or drop dead. (Which is another serious weakness tbh.) Maybe shadow striders value their privacy and political autonomy too much to take those kinds of risks. They're going to set up shop on the outskirts of a small-to-midsize human settlement, and commence to apex predator-ing.
The main principle here is: turn the humans against each other to divert suspicion. HOW, you say? Many different methods can be used by our highly flammable human-eating insect friendos! The most casual of glances at human history shows that we can always be convinced to throw other humans under the bus - and even be happy about it.
Just snatch travelers off the road, people who stray too far into the woods... could start with actual human bandits, come to think of it. They could probably get away with it for awhile before the humans got suspicious. But people would eventually figure out what was going on.
Start a cult.
A dangerous, but in some ways very easy option. Among humans there are always a few hopeless souls who will follow ANY being who notices them and makes them feel important. Downtrodden folks with nothing left to lose. Lovers whose beloveds have died, or betrayed them. Or vanished mysteriously in the night without a trace - hey, sometimes you gotta make your own luck! Wealthy people whose power has left them jaded and empty inside. People who would LOVE, in other words, to be told that sacrificing themselves (or their friends - or their enemies!) to the spooky and otherwordly insect queen deep in the hills will REALLY make them feel special.
Or heck, the striders could lie and say that any human they eat will be reborn as a strider, through the magic of caring. The humans won't know the promise is false until it's much too late!
The thing that makes this route risky, of course, is that it starts rumors. Rumors of the kind that are sure to eventually attract paladins. Or mobs of enraged peasants with torches. Or both.
Exploit existing cultural conflicts among the humans.
In particular, ones that cause people to distrust and be suspicious of the clergy, paladins, the crown etc. Are local clerics or royal agents corrupt, squeezing extra donations or tribute out of farmers in a year of drought, feasting while the people starve? Are there older religious traditions that were sidelined or forcibly stamped out to make way for the current main religion? Are there different cultures present in the region, old hostilities that people cling to, or longstanding power imbalances among different groups of humans?
Get the humans to fight against each other, and no one will believe it was REALLY freaky bug people from the back of beyond. It was Shelbyville. Or Desert Bluffs. Or the Joneses next door, with their snooty attitude and their shiny new fence.
Foment civil unrest.
A little more risky, but still plays into the humans' hostilities towards one another and potentially allows the striders to escape detection.
- Steal some peasants away in the night, but make it look like the duke's guards did it. Assassinate (and carry off) a few guards, and make it look like the work of unruly peasants.
- Do a bunch of false flag attacks that point in multiple directions at once. Get the folks from the hills riled up by stealing away youngsters who'd been hanging out with slick customers from the valley. Steal away fresh young valley kids who'd been spending time with those no good yokels from the hills.
Once a feud between groups of humans has started, everyone will be sure all the mysterious disappearances are the other faction's fault. Rumors of striders are just nonsense designed to make them forget about the REAL enemy.
Bribe members of privileged groups to sacrifice people they are oppressing.
This is the lowest-risk option for our shadowbugs, because it does something the human society is already doing. They're just doing it a wee bit faster, with a moderate increase in blood and screaming. The cave system they live in probably has precious gems and minerals they can use to bribe those who crave wealth. Those who crave power might want to use the striders' invisibility to do a bit of espionage. Others will be delighted to have hidden assassins who are happy to eliminate their political enemies for free.
- Local baron's tenant farmers can't pay the rent? He takes the plumpest, healthiest family member instead and sends them to the striders in exchange for a heap of gold or jewels.
- Local cleric is in hot water cause she's been embezzling the church's funds to line her pockets? The stealthy and fast-moving striders can not only eliminate the investigator who was about to uncover it - they can also help make it look like he was dabbling in forbidden sorceries. And encourage her to find more... "heretics," among the more suspicious of the townsfolk.
- Local merchant is getting run out of business by a rival whose goods are cheaper and of better quality? Maybe their workers are underpaid and threatening to unionize? The striders are happy to pose as human "bandits" who mysteriously made off with all the troublesome people, while the trade goods find their way into the merchant's warehouse.
BUT my personal favorite would be
All of the above!
If I were a hive queen, I'd want to start out with straightforward banditry. My babies need snacks, and we're all going to be working very hard during the initial setup phase. Ideally we could find a couple of prosperous bandit gangs, and make occasional judicious raids on merchant caravans to mimic their tactics for awhile and keep our larders full. This would have the added benefit of gaining us a stockpile of human treasure for later bribery purposes.
My "cult" activities would be sporadic and extremely limited. Although we would eventually eat the people who were tricked into worshipping me, my MAIN goal would be to pump them for information about the factional divisions in the region. Heck, I might even keep one or two alive a little bit longer to act as my spies.
With the help of my workers and perhaps our human spies, I would then start sowing disinformation among the humans to turn them against each other. Once the factional anger and distrust reached a boiling point, then we would start to disappear people. My babies would feast! It would be delightful!
Of course, the feast of discord can only last so long. Civil unrest can't get TOO out of hand, or else it'd bring down royal troops and clerics who would be likely to scour the countryside. Can't have that. So we would stop for a little while. Maybe have our spies work to foment peace instead, just to keep it interesting.
However, the course of the conflict would have revealed who the real power players are in the local scene. People who, rather than taking a principled stand or helping others, instead found a way to leverage the misery of others for their own personal gain. Those are the individuals we would approach with offers of bribery.
Bribing powerful folk to get us access to various people they held in sway would tide us over for a peaceful while. The normal order of things would re-establish itself. Human bandits would once again start to prey on their fellow bipeds, and hide out in various places in the hills. People would forget about the rumors of shadowy, fast-moving creatures in the dark, and dismiss them as wild speculations during the time of civil unrest.
Then, when everyone felt it was finally time to relax, we would do it all again.