Despite the important role of fine particle agglomerates in nature and powder technology, the physical mechanisms underlying their strength are still not well understood. In particular, the effects of particle shape in association with cohesive-frictional interactions between particles remain to be elucidated on a quantitative basis. We use particle dynamics simulations to create agglomerates composed of hexapod-shaped particles and analyze their mechanical behavior under diametral compression to showcase the effect of non-convex particle shape and interlocking on their compressive strength. Two different regimes are identified as a function of hexapod aspect ratio. In the first regime, where the hexapods are featured by their rough surface, the strength of the agglomerate is primarily controlled by cohesion at the contact level. In the second regime, where the hexapods are characterized by their long arms that can interlock, the tensile strength at the local level is scaled up by orders of magnitude to yield a high compressive strength at the scale of the agglomerate. We demonstrate that this amplifying effect of interlocking is enhanced by friction coefficient between hexapods, which hinders their disentanglement under the action of the external load.