After drinking yet another half a dozen cups of tea while waiting for both kernel-devel and kernel-devel-smp to install, I have an idea how to fix this mess:
1) Add one more file to kernel-devel and kernel-devel-smp packages, whose contents are the output of:
cd $RPM_BUILD_ROOT/usr/src/kernels/<<version>> find . -type f -print | sort | xargs md5sum >../<<version>>.md5sum
2) %post would then simply read all .md5sum files, reconcile them, and know exactly what to hard link.
I'd be surprised if this will not speed things up by at least a factor of 10.