I assume you want to deny the execute right not only to these folders but to the whole tree starting from them (otherwise, there is no point in doing what you want to do).
The - obvious - consequence will be that any executable located in these will fail to run.
Unfortunately, this will include a rather large number of legitimate applications.
%localappdata% and %appdata% are the most problematic ones: Dropbox, Chrome, SkyDrive, for instance, will fail to work. Most automatic uploaders and many installers will also fail to work.
%UserProfile% is even worse since it includes both %localappdata% and %appdata% as well as a number of other folders.
In short: if you prevent applications from running from these folders, your system might get pretty much unusable.
%temp% is different. While you might occasionally have legitimate programs running from there, it's quite infrequent and usually easy to work around. Unfortunately, %temp% expands to different folders depending on the user context you're expanding it from: it might end up in %localappdata%\temp (in the context of a user) or %SystemRoot%\temp (in the context of the system) so you will have to secure each location individually.
%temp% is also a good candidate because that's where most mail programs will save attachments before opening them: that will help in many cases of mail-based maleware.
One good trick is to change the premissions on the C:\Users\Default\AppData\Local\temp and C:\Users\DefaultAppPool\AppData\Local\Temp folders when you setup the system (and, of course, %SystemRoot%\temp). Windows will copy these folders when it creates new profiles and so new users will have a secured environment.
You might want to add %UserProfile%\Downloads to your list: this is where most browsers will same the user's downloaded files and denying execution from there will also increase security.