If you need to secure the bolts, something like a repair ring drilled into the concrete should do that.
You can have the bowl pointing downward, it does mean that more water stays in the bowl before it is flushed out.
That's better than having the end of the bowl high, and leaving little water in the bowl.
You do have to get rid of the rocking.
If you do wind up shimming more in the front, then some people use caulk or grout.
I wouldn't try to shim it at 1/2" though, that is a lot.
I would lean it some to reduce the amount of shim.