Bio-based solutions for solid timber gluing have always been a very sensitive topic in wood technology. In this work, we optimize the gluing conditions of a starch–tannin formulation, which allows high performance in dry conditions and resistance to water dipping for 3 h, allowing for the D2 classification to be reached according to EN 204. It was observed that the starch–tannin formulations enhanced their performance by increasing the heating temperature, achieving satisfactory results at 140 °C for 13 min. The proportion of polyphenols in the mixture enhances the water resistance but is only tolerated until 20–30%. In particular, the addition of 10% tannin–hexamine enhances the water-resistant properties of starch for both quebracho and chestnut extract. The application of the jet of cold atmospheric plasma allows for good results with more viscous formulations, increasing their penetration in wood. Solid-state 13C-NMR analysis was also performed, and the spectroscopic information suggests establishing a coordination complex between starch and tannin.