Traditional simulation-based protein design considers energy minimization of candidate conformations as a singleobjective combinatorial optimization problem. In this paper we consider a challenging protein design problem, producing twelve protein species based on collagen that uniquely assort into four groups of three: a problem defined herein as a 4-level heterotrimer. We formulate a bi-objective combinatorial minimization problem that targets both stability and specificity of the 4-level heterotrimer. In order to approximate its Pareto frontier, we utilize both evolutionary and non-evolutionary approaches, operating in either Pareto or aggregation fashions. Our practical observations suggest that the SMS-EMOA with Evolution Strategies' operators is more effective than standard heuristics deployed in computational protein design, such as Simulated Annealing, Replica Exchange or the Canonical Genetic Algorithm. We investigate the attained Pareto optimal sets using Barrier Tree analysis, aiming to provide insights into the chemical search-space, as well as to explain the observed algorithmic trends. In particular, we identify Replica Exchange as a promising non-evolutionary technique for this problem class, due to its efficient exploration capabilities. Overall, a common high-level protocol for simultaneous landscape analysis of evolutionary and non-evolutionary search methodologies is put forward for the first time.