I feel that chicken feeds should really have a source of animal protein (fish meal, etc.) but this is becoming less and less common. chickens are certainly not naturally vegetarian; they eat every bug they can catch. But vegetable protein is better than nothing. Many people feed their chickens mealworms, for one because they love them. Meat scraps from your table are good, if they can swallow the pieces without a problem. Less expensive sources at the store are canned mackerel or the carcass or bone from a roast, or roast chicken or turkey.. Black Oil Sunflower Seeds (BOSS) are often touted as a snack, partly for their protein content, but as far as I can find, it's only about 15% which is little or no better than most feeds. It does give you a snack to use in place of scratch, though. Most scratch mixes are quite low in protein. Another good source of vegetable protein is game bird feed. You coud actually switch to it for a while, or mix some into their regular feed.
One way that their diet can get protein deficient is actually by accident, in giving a lot of "treats' that don't have protein, thus diluting the overall protein intake. Many people give greens, fruit and veggie peelings, etc. which help distract them and help with boredom, and of course they love eating many of these foods -- but it's good to keep in mind that most "treats" are not high in protein. Of course, chickens don't require a treat at all, but many owners take a lot of pleasure in giving them, as well as using them to train the birds to come when called.
HERE is BYC's treats chart., in case you haven't found it and it can be of some use to you. Note the comment about cat food at the bottom.