Most vegan diets are adequate for health (provide all essential amino acids) without any particular focus on protein combining. A poorly planned vegan diet may be deficient in lysine, but this can be compensated by eating foods rich in lysine such as soybean products and other legumes.
Some people with specific dietary goals like increasing muscle mass or losing fat may benefit by combining foods to optimize intake of amino acids.
The protein combining myth
The concept that combining proteins within a single meal is essential was first popularized in 1954 by American nutritionist Adelle Davis in her book Let's Eat Right to Keep Fit. These are her words:
If two or more incomplete proteins are eaten at the same meal, one may supply the amino acids lacking in another, and together they may make a valuable contribution to health. ... Dr. Cannon² has shown, however, that if half the essential amino acids are eaten at a certain time and the other half taken only one hour later, the body does not build protein with them. (p.29)
Davis is referencing a 1950 study by Paul R. Cannon titled Recent Advances In Nutrition. Cannon originated the idea that all amino acids must be eaten together in the same meal, but there are some concerns with the study. The rats were fed two alternating rations in which five essential amino acids had been totally removed, but this does not reflect any real food consumed by humans. A later publication by Waterlow et al. in 1978 showed that free phenylalanine in the human body corresponds to only about 1.5 hours worth of protein synthesis, so the poor growth of rat subjects is explained by phenylalanine deficiency when partial rations were separated by 2 hours or more. All plant proteins provide phenylalanine in abundance, so Cannon's study cannot be considered reflective of humans eating a realistic diet.
But if protein combining within meals isn't necessary, how much leeway do we have? Because some plant foods provide less lysine, free storage of lysine is an important consideration. It turns out that the body stores about 20 times more lysine than phenylalanine (based on protein free ratio) so we have a window of roughly one day (24 hours) in which to meet our lysine requirement.
The "incomplete" protein
It's worth considering what protein "completeness" really means, because the notion of protein combining only makes sense if some proteins are indeed inadequate.
All essential amino acids are available in plant proteins, although the levels vary between foods. Classifying some proteins as incomplete gives the false impression that certain amino acids are absent, when in fact they are still present in similar quantities. Incomplete proteins are commonly said to "lack" a specific amino acid, which is often incorrectly interpreted as meaning the amino acid is missing. The degree to which we have internalized this misconception is shown in Tom Kelly's answer to this question where he incorrectly writes:
Incomplete protein sources aren't a bad thing. You just can't live entirely on only one.
The falsity of that statement can be shown with a counterexample. Consider lentils, for example. Even though lentils are labelled as "incomplete" it is still quite possible to meet requirements for all essential amino acids by eating only lentils, with plenty of space left in the diet to add other foods.
The point is that protein completeness exists on a spectrum, and our intuitive understanding would be improved if we instead used the words "complete" and "mostly complete".
Increasing muscle or losing fat
People who are trying to lean out their body composition, either by increasing muscle or losing fat, may benefit by consuming a more optimal balance of amino acids.
When aiming for weight loss the goal is to restrict energy intake (eat fewer calories) but still maintain intake of protein sufficient for normal body processes. Because most vegan sources of protein (especially whole food sources) come with additional energy in the form of carbohydrates, an imbalance of amino acids is associated with extra energy intake. This presents an opportunity to reduce energy intake by optimizing amino acid balance -- in other words, protein combining. The goal is to minimize calories while maximizing limiting amino acids. This particular minimax scenario was the subject of a 2011 study by Peter J. Woolf et al. in which they developed a web-based optimizion tool called vProtein and discovered several unconventional protein pairings.
Overall, the most efficient pairings include sweet corn/tomatoes, apple/coconut, and sweet corn/cherry. The top pairings also highlight the utility of less common protein sources such as the seaweeds laver and spirulina, pumpkin leaves, and lambsquarters.
Similarly, people aiming to build muscle (bodybuilders especially) will want to maximize the availability of all amino acids consumed. Because some very muscular people may be limited by the amount of food they can eat, optimizing amino acid balance allows for maximum myogenesis, or "big gains".
Highly processed diets and the role of protein foods
A diet that is full of refined carbohydrates and oils is going to be correspondingly lower in protein. This is what gives rise to the importance of "protein foods". Proponents of a whole food plant based diet correctly point out that protein is abundant in vegetables, and a whole food diet draws on many sources of amino acids. However a junk food vegan will be eating fewer whole foods and have fewer sources of protein, necessitating inclusion of more meat substitutes like tofu, protein powder, seitain, etc.
Practical advice for vegetarians and vegans
Because our bodies have a limited short-term reserve of certain amino acids (up to a day's worth) and because all essential amino acids are included in all plant proteins, it's actually quite simple to meet protein and amino acid requirements on a vegan diet. As mentioned earlier, lysine is most likely to be deficient on a vegan diet, so ensuring sufficient intake of lysine during the day pretty much covers all the bases.
We can see the result of this in Canada's Food Guide which recommends 3 servings of meat alternatives (legumes and soy products) per day. The very popular Dr. Greger provides the same advice in his Daily Dozen Checklist where he recommends 3 servings of beans per day.
And the same message is repeated by American Dietetic Assocation in their position statement on vegetarian diets.
Dietary adjustments such as the use of more beans and soy products in place of other protein sources that are lower in lysine or an increase in dietary protein from all sources can ensure an adequate intake of lysine.