Bluetooth HC-05(ZS-040) not found by Android phone

@grrigore
I am really trying to understand why you started your bluetooth experience with an AT adventure and have an ongoing focus on AT mode?

http://forum.arduino.cc/index.php?topic=546523.msg3725616#msg3725616

These modules should work out of the package. Did someone previously use the module, and you are trying to get it back to defaults. Are you trying to change some operational parameters?