We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items. In the first stage, we select the optimal dimensions of the boxes, while in the second stage, the items demanded are assigned to the selected box types, with the goal of minimizing unused volume. To solve this two-stage problem, we propose a cutting plane approach using Benders decomposition, where the master problem essentially corresponds to the first stage. Due to the specific structure of the second-stage problem, we are able to generate the resulting Benders cuts by a purely combinatorial algorithm. Moreover, this allows us to apply column generation, as the coefficients of the constraints of the new variables can also be derived directly from the combinatorial structure. Since the number of available box types is huge in practice, the combination of both procedures provides a particularly promising approach.