The performance cost of that would be horrifying, as it'd force the linker to do all sorts of unnecessary work whenever it executed any process. Like, say `ps', `ls', `as', `gcc', etc.
You might be able to avoid that by borrowing a spare (if there is one) ELF header flag to indicate "this is a desktop application".
In all honstly, though if you're going to mangle things that much why not take NextSTEP / Apple's approach of .app dirs with self-contained metadata?
Anyway, none of these proposed solutions address things like users wanting to make their own app links, make custom launchers with different arguments to apps, add launchers for apps they've compiled themselves, etc. Making .desktop files require execute permissions would be a big step.