Looks like selinux-policy-devel does not pull in m4 that is required to build modules. From mock builds in rawhide and f18: + make NAME=mls -f /usr/share/selinux/devel/Makefile /bin/sh: m4: command not found
Fixed in selinux-policy-3.11.1-57.fc18
selinux-policy-3.11.1-57.fc18 has been submitted as an update for Fedora 18. https://admin.fedoraproject.org/updates/selinux-policy-3.11.1-57.fc18
Package selinux-policy-3.11.1-57.fc18: * should fix your issue, * was pushed to the Fedora 18 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing selinux-policy-3.11.1-57.fc18' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/FEDORA-2012-19374/selinux-policy-3.11.1-57.fc18 then log in and leave karma (feedback).
Package selinux-policy-3.11.1-59.fc18: * should fix your issue, * was pushed to the Fedora 18 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing selinux-policy-3.11.1-59.fc18' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/FEDORA-2012-19374/selinux-policy-3.11.1-59.fc18 then log in and leave karma (feedback).
Package selinux-policy-3.11.1-60.fc18: * should fix your issue, * was pushed to the Fedora 18 testing repository, * should be available at your local mirror within two days. Update it with: # su -c 'yum update --enablerepo=updates-testing selinux-policy-3.11.1-60.fc18' as soon as you are able to. Please go to the following url: https://admin.fedoraproject.org/updates/FEDORA-2012-19374/selinux-policy-3.11.1-60.fc18 then log in and leave karma (feedback).
selinux-policy-3.11.1-60.fc18 has been pushed to the Fedora 18 stable repository. If problems still persist, please make note of it in this bug report.