The cytoskeleton of eukaryotic cells provides mechanical support and governs intracellular transport. These functions rely on the complex mechanical properties of networks of semiflexible protein filaments. Recent theoretical interest has focused on mesoscopic properties of such networks and especially on the effect of local, non-affine bending deformations on mechanics. Here, we study the impact of local network deformations on the scale-dependent mobility of probe particles in entangled networks of semiflexible actin filaments by high-bandwidth microrheology. We find that micron-sized particles in these networks experience two opposing non-continuum elastic effects: entropic depletion reduces the effective network rigidity, while local non-affine deformations of the network substantially enhance the rigidity at low frequencies. We show that a simple model of lateral bending of filaments embedded in a viscoelastic background leads to a scaling regime for the apparent elastic modulus G(omega) sim omega^{9/16}, closely matching the experiments. These results provide quantitative evidence for how different a semiflexible polymer network can feel for small objects, and they demonstrate how non-affine bending deformations can be dominant for the mobility of vesicles and organelles in the cell.