The present study aimed at exploiting the unfavorable changes of thermally modified shellac with the idea of developing starch/shellac-based composites intended for food contact applications. On baking shellac samples at 200°C for different time intervals (0–20 min), functional groups and linkages were drastically modified, especially anhydride formation, polyesterification, and ether/acetyl linkage occurrences. These processes caused a marked increase in the glass transition temperatures (from about 33 to 60°C) and melting temperatures (from 175 to about 230°C) but a decreased solubility in ethanol (from 95 to 9%). The addition of shellac into a starch-based formulation for producing shaped bodies in combination with heat could significantly strengthen the composite materials and drastically reduce the water uptake after soaking in both cold water and hot water. Furthermore, application of a food-grade biodegradable coating showed remarkable improvement in terms of water resistance and mechanical strength of the composites. The first attempt at making chopsticks was successful and showed promising results. Nevertheless, forming processes and mold designs of such articles—long narrow tubes—need further study.