The easiest way is to set the execute permissions yourself. cd to the directory you want to set the files (/usr/kde/bin) or something like that. From there, enter the following command
find . -name "*" -exec chmod +x {} \;
That will set the owner permission to execute for all files within that directory. The +x can be expanded to +xxx if you want to set execute permissions for everyone, but I think the kde executables only have to be set for owner.
As to why, it is probably your umask setting. Check the .profile and find the umask line. This is used to set your initial file permissions and is a takeaway option. File permissions are based on 4 = Read, 2 = Write and 1 = Execute and 3 sets of these numbers for owner, group and world. Example - 754 would mean owner read, write, execute; group would have read + execute and everyone else would have read only. umask changes your defaults by removing permissions. As an example, if your umask is 111 all files created would have the execute permission turned off, no matter how often you tried setting them. Your umask should always start with a zero and yours probably does not.
Good Luck!