How do large herbivores get enough protein?
It boils down to the anatomy.

Herbivores are very good at digesting plant matter, which us monogastrics are not particularly good at. Many herbivores (such as ruminants) have large, highly developed gastrointestinal tracts containing symbiotic bacteria to allow them to digest plant matter. Once the cellulose in the plant cell walls is digested, the animal can then access the nutrients  contained in the plant matter to a degree we cannot. Ruminants (such as cows) are even better able to absorb nutrients in this way than monograstric herbivores (such as horses). Rumen microbes are also an important source in ruminants for production of amino acids.

There's also a reason why the GI tract of these herbivores is so big. In the cow, it's an enormous rumen. In the horse, it's a massive colon for hindgut fermentation. To get all the nutrients they need - such as amino acids - these herbivores have to consume and ferment vast quantities of plant matter. A carnivore can generally get all the nutrients it needs in a much smaller meat meal, meaning it does not need such an extensive GI tract.  

Different species, of course, have different metabolic demands and corresponding nutritional needs. Cows and other herbivores cannot synthesize all the amino acids they need, meaning they have to be consumed through the diet. Though it is somewhat dated, an interesting discussion on this subject is Protein and Amino Acid Requirements of Mammals (PDF) by Anthony Albanese (1950). The author goes through in great details the different protein requirements for various species, but I will bring your attention to one interesting table on p 116 as it is pertinent to your last question:



As you can see, the protein content of milk seems to correspond with the time to double birth weight. Cats with a high protein milk grow very quickly, while cows, horses, and humans grow comparitively more slowly (and thus have lower protein milk).

All animals have to get protein or amino acids through the diet, but they just have different methods to satisfy their metabolic requirements. For carnivores, they consume small protein-packed meals. For large herbivores, they have to consume and digest large quantities of plant matter to meet their needs.