Using a hybrid method based on fermionic diagonalization and classical Monte Carlo techniques, we investigate the interplay between itinerant and localized spins, with competing double- and superexchange interactions, on a honeycomb lattice. For moderate superexchange, a geometrically frustrated triangular lattice of hexagons forms spontaneously. For slightly larger superexchange a dimerized ground state is stable that has macroscopic degeneracy. The presence of these states on a nonfrustrated honeycomb lattice highlights novel phenomena in this itinerant electron system: emergent geometrical frustration and degeneracy related to a symmetry intermediate between local and global.