Hmm... I never had that problem, so I'm just making guesses: You might want to check if a button is stuck. That hasn't happened to me ever, but as you tried everything else I would have recommended (the "official" troubleshooting and rebooting, not sure if it's a good idea to reset the BIOS for every error) I'd push the Start plus and minus buttons a few more times with a bit more force, just in case. Also the green button on the back!
Then change into a higher user group and activate the Start-Up mode (where it overrides the X11 safety, but only allows T1), just to see if it changes anything when you run a program.
Finally, go into the safety settings, change something and then change it back, as BCO is a safety-relevant feature maybe it helps.
Last idea: Select a program and then do block selection on an axis movement - could be just the first axis movement, or another one further down.
If that doesn't help, get in touch with the KUKA hotline, they are usually really quick with those obscure problems.
Please let us know what helped!