On a homebrew livecd:

...
[    9.288452] systemd-tmpfiles[805]: Successfully loaded SELinux database in 8ms 279us, size on heap is 468K.
[    9.430335] type=1400 audit(1316020731.067:3): avc:  denied  { write } for  pid=805 comm="systemd-tmpfile" name="cache" dev=dm-0 ino=13 scontext=system_u:system_r:systemd_tmpfiles_t:s0 tcontext=system_u:object_r:var_t:s0 tclass=dir
[    9.430344] type=1400 audit(1316020731.067:4): avc:  denied  { add_name } for  pid=805 comm="systemd-tmpfile" name="man" scontext=system_u:system_r:systemd_tmpfiles_t:s0 tcontext=system_u:object_r:var_t:s0 tclass=dir
[    9.430358] type=1400 audit(1316020731.067:5): avc:  denied  { create } for  pid=805 comm="systemd-tmpfile" name="man" scontext=system_u:system_r:systemd_tmpfiles_t:s0 tcontext=system_u:object_r:var_t:s0 tclass=dir
[    9.433407] type=1400 audit(1316020731.070:6): avc:  denied  { relabelfrom } for  pid=805 comm="systemd-tmpfile" name="man" dev=dm-0 ino=131073 scontext=system_u:system_r:systemd_tmpfiles_t:s0 tcontext=system_u:object_r:var_t:s0 tclass=dir
[    9.825863] livesys[829]: /etc/init.d/functions: line 58: /dev/stderr: No such device or address
[    9.910265] SELinux: initialized (dev tmpfs, type tmpfs), uses transition SIDs
[    9.911437] SELinux: initialized (dev tmpfs, type tmpfs), uses transition SIDs
[    9.912481] SELinux: initialized (dev tmpfs, type tmpfs), uses transition SIDs
...

I do not have man-db installed and do thus not have /var/cache/man ... but here in permissive mode it seems like systemd creates it because of the /usr/lib/tmpfiles.d/systemd.conf entry.

I guess that it could be argued that the policy is right and the problem should be fixed elsewhere. Perhaps:
* systemd could require man-db ... no ... please don't
* /var/cache/man could move to filesystem ... yes, perhaps
* systemd shouldn't create non-existing directories ... also an option

selinux-policy-targeted-3.10.0-28.fc16.noarch
kernel-3.1.0-0.rc6.git0.0.fc16.x86_64
dracut-013-8.fc16.noarch
systemd-35-1.fc16.x86_64