Hi Ondřej @Paker ,
Is your Cube set to Shade Smooth, maybe? (Doesn’t look like it, but…?) Shade Smooth By Angle would then be a better option.
There’s actually quite a lot that can go wrong with Booleans, but this doesn’t look like a major thing. But I can’t reproduce the result, so maybe you can post a link to your .blend file (via Dropbox, GoogleDrive, or so). That is if Dwayne didn’t already solve the problem, of course.
