The fundamental mechanism responsible for optically induced magnetization dynamics in ferromagnetic thin films has been under intense debate since almost two decades. Currently, numerous competing theoretical models are in strong need for a decisive experimental confirmation such as monitoring the triggered changes in the spin-dependent band structure on ultrashort time scales. Our approach explores the possibility of observing femtosecond band structure dynamics by giving access to extended parts of the Brillouin zone in a simultaneously time-, energy- and spin-resolved photoemission experiment. For this purpose, our setup uses a state-of-the-art, highly efficient spin detector and ultrashort, extreme ultraviolet light pulses created by laser-based high-order harmonic generation. In this paper, we present the setup and first spin-resolved spectra obtained with our experiment within an acquisition time short enough to allow pump-probe studies. Further, we characterize the influence of the excitation with femtosecond extreme ultraviolet pulses by comparing the results with data acquired using a continuous wave light source with similar photon energy. In addition, changes in the spectra induced by vacuum space-charge effects due to both the extreme ultraviolet probe- and near-infrared pump-pulses are studied by analyzing the resulting spectral distortions. The combination of energy resolution and electron count rate achieved in our setup confirms its suitability for spin-resolved studies of the band structure on ultrashort time scales.