In the context of string dualities, fibration structures of Calabi-Yau manifolds play a prominent role. In particular, elliptic and K3 fibered Calabi-Yau fourfolds are important for dualities between string compactifications with four flat space-time dimensions. A natural framework for studying explicit examples of such fibrations is given by Calabi-Yau hypersurfaces in toric varieties, because this class of varieties is sufficiently large to provide examples with very different features while still allowing a large degree of explicit control. In this paper, many examples for elliptic K3 fibered Calabi-Yau fourfolds are found (not constructed) by searching for reflexive subpolyhedra of reflexive polyhedra corresponding to hypersurfaces in weighted projective spaces. Subpolyhedra not always give rise to fibrations and the obstructions are studied. In addition, perturbative gauge algebras for dual heterotic string theories are determined. In order to do so, all elliptically fibered toric K3 surfaces are determined. Then, the corresponding gauge algebras are calculated without specialization to particular polyhedra for the elliptic fibers. Finally, the perturbative gauge algebras for the fourfold fibrations are extracted from the generic fibers and monodromy.