gnu profiler for Nios application, which compiler optimization level to choose

You have to think about what you are trying to measure.

The usual reason for considering profiling something is because you want to make it run faster - and profiling might identify the slow parts that are worth further investigation.

You'll get a big gain from using -O3, so there is no point profiling without it, you'll be measuing something else.

Profiling isn't necessarily the best tool for optimising simple algorithms. I would consider looking at how many clocks it takes to get from the start to various intermediate points, and then the end. That will give more stable results than timer-tick based profiling, although the effects of instruction and data caches, and the branch predictor state will still give some variation.

Speeding up AES probably needs careful inspection of the generated code, and possibly the addition of some 'helper' custom instructions.