I think all the other answerers have missed the most obvious, and foolproof, solution - make the cows apex predators themselves. Virtually no land herbivores are, under natural conditions, free from predation - elephants may seem to be so, but that's only because humans have wiped out a bunch of megafauna-specialist lineages (e.g. sabertooth cats), and apparently caused a trend in lower average size in large hypercarnivores across the globe.
Even fully-grown Paraceratherium, the largest land mammals ever, evidently were preyed on by giant Crocodylus bugtiensis. Blue whales are immune to predation as adults (and orcas do prey on them when they're subadults), but you can't get anything the size of a blue whale which still looks like a cow. So, in my opinion - herbivory is not an option. Instead, let the cows reside at the top of the food chain.
Herbivorous animals have turned carnivorous numerous times in Earth's history. Among mammals, there are the mesonychids, entelodonts and relatives, early whales, and even a species of pig called Tetraconodon. There's also an ankylosaur called Laoiningosaurus which some hold is piscivorous. Deer, hippos, boar and indeed cows also consume meat from time to time.
They still might look like cows. If this was a burly, bear-like predator, it would have the classic stocky bovine build, and it could still have horns, too - there are plenty of horned predators in history, mainly reptiles, but also mammals! Take, for example, Pyrokerberus necrobotris, a mesonychid carnivore with horns, or to be more specific, ossicones.
Artwork by Hodari Nundu on Deviantart.
TL;DR: I think that having the bovines evolve into apex predators is the best solution. It's more plausible than it sounds.