We use simulations of large-scale structure formation to study the build-up of magnetic fields (MFs) in the intergalactic medium. Our basic assumption is that cosmological MFs grow in a magnetohy-drodynamical (MHD) amplification process driven by structure formation out of a magnetic seed field present at high redshift. This approach is motivated by previous simulations of the MFs in galaxy clusters which, under the same hypothesis that we adopt here, succeeded in reproducing Faraday rotation measurements (RMs) in clusters of galaxies. Our ACDM initial conditions for the dark matter density fluctuations have been statistically constrained by the observed large-scale density field within a sphere of 110 Mpc around the Milky Way, based on the IRAS 1.2-Jy all-sky redshift survey. As a result, the positions and masses of prominent galaxy clusters in our simulation coincide closely with their real counterparts in the Local Universe. We find excellent agreement between RMs of our simulated galaxy clusters and observational data. The improved numerical resolution of our simulations compared to previous work also allows us to study the MF in large-scale filaments, sheets and voids. By tracing the propagation of ultra high energy (UHE) protons in the simulated MF we construct full-sky maps of expected deflection angles of protons with arrival energies E = 1020 eV and 4 X 1019 eV, respectively. Accounting only for the structures within 110 Mpc, we find that strong deflections are only produced if UHE protons cross galaxy clusters. The total area on the sky covered by these structures is however very small. Over still larger distances, multiple crossings of sheets and filaments may give rise to noticeable deflections over a significant fraction of the sky; the exact amount and angular distribution depends on the model adopted for the magnetic seed field. Based on our results we argue that over a large fraction of the sky the deflections are likely to remain smaller than the present experimental angular sensitivity. Therefore, we conclude that forthcoming air shower experiments should be able to locate sources of UHE protons and shed more light on the nature of cosmological MFs.