The goal of this work was to improve the barrier properties of selected papers against water, grease and oil or gases (water vapor and oxygen) by covering them with biodegradable commercial coating carriers based on cellulose nanocrystals (CNCs) and polyvinyl alcohol (PVOH). The aim was also to obtain cellulose recyclable packaging materials with improved barrier characteristics. The properties of paper coatings based on CNCs and PVOH were characterized. Various paper coating techniques (flexographic printing, rotogravure printing and blade printing) were evaluated with respect to the final properties of the surface-modified paper with different starting grammages (40 g/m², 70 g/m², 100 g/m²). Functional properties, such as the barrier against oxygen, water vapor, water and grease; mechanical properties; and seal characterization of coated paper were examined. The results of this study demonstrated that the covering of the paper may improve the water, grease and oil barrier and that the best results were obtained for Gerstar 70 g/m² coated with J12 coatings using the flexographic technique.