Allright, it works now :-)
Apparently the HD 4xxx series got a problem with the 13.1 OpenCL stuff, so I installed 12.6 and then only installed the 13.1 display driver (and use the 12.6 OpenCL version). Now it works fine, thank you very much for your great and fast support!