Those creases are basically the result of there not being enough geometry for the normals to be averaged smoothly over the mesh.
It would be helpful to know what exactly you're doing here. Is this a model you're working on, and can change? Or is this an imported model you're modifying? If this model is the low poly version of a game asset, then those creases could potentially be corrected by a normal map.
If you want smooth normals without resorting to a normal map, you need sufficient geometry to support that. This basically means a loop of faces around hard edges, or in your case holes.