Epaulette sharks are known for their terrestrial habits, which can "crawl" across the land like this:
Much like an ancient Tetrapodomorph, they crawl with their pectoral and pelvic fins. They can survive for impressive periods in environments with little to no dissolved oxygen, such as the land.
Now we know it's possible, we should address how fully terrestrial sharks would evolve.
Why they would do it:
Our friend the epaulette lives in very shallow reefs, which are exposed to the air when the tide goes out. Where most other competitors would retreat to deeper waters, it stays, crawling across the land to feed where other predators can't go, and its prey stands little chance of escape in such enclosed tide pools.
If, in the future, a shark like this would live in an environment of many pools with areas of land connecting them, it might crawl between pools in search of prey.
Another idea is that it might become a water-to-ground predator, like a crocodile. If a potential, unexploited prey source lived on beaches, it could start out by beaching itself like a killer whale, but then evolve to be able to stay on the land a bit longer. After millions of years, the terrestrial habit becomes more and more refined, until they are fully able to go on land.
How they would breathe:
Bony fish have an organ called a swim bladder, which is an offshoot of the digestive system. It's believed that when fish colonized the land and became tetrapods, their swim bladders evolved into lungs.
Sharks lack a swim bladder to rig up, so we're gonna need some other method of air-breathing. Some arthropods have something called a book lung.
The way a book lung works is that oxygen passes through a slit, and then proceeds through a multitude of folds. Blood circulates through the lung, exchanging carbon dioxide for fresh oxygen.
Now, this is where it gets really speculative. Sharks have an organ in their gut called a spiral valve, which looks like this:
If they were somehow to bifurcate this spiral valve, keeping one as part of the digestive system, while another would form some sort of book lung equivalent, then they might be able to breathe air, through holes that are actually modified gills. Again, remember that this is the kind of wacky speculation that I enjoy, but others may frown upon.
What they would look like:
When we look at the epaulette shark and how it moves, it's clear that they're using their pectoral and pelvic fins to walk. So did the first tetrapodomorphs, so it's probable that a terrestrial shark would have four legs.
If an epaulette-like shark was to colonize the land, I predict that:
- It would have four limbs with digits
- Its dorsal fins would be lost
- Its tail would atrophy
I think it would have digits because, looking at a shark skeleton, they have rays of cartilage in their fins which would become useful for walking. They wouldn't need their dorsal fins (Unless they were display organs) because they wouldn't swim much, and they don't need such a long, powerful tail on land.
One thing that would have to happen is ossification. Obviously, shark skeletons are made of cartilage, and cartilage might not be suitable for supporting a land animal of the shark's size. So, I'd be surprised if terrestrial sharks didn't ossify their cartilaginous supports and gain a full-fledged calcium phosphate skeleton.
How they would match your description:
In this scenario, I spoke of the sharks coming on to the land as predators, but a descent from carnivory to omnivory to herbivory is certainly possible. After all, plants carpet the land far more than the water, so it's an abundant food source for the shark to exploit.
As for insectivory, that's also possible. Depending on how they catch the insects, they might develop a good sense of smell and sharp claws. As for size, epaulettes are pretty small, about the size of a dog.
Anyway, those are my thoughts on how terrestrial sharks would evolve. I hope I answered to your satisfaction.