If I create new folders for storage - do I need to change the permissions for them? (all rules-777 / all rules - rwx)
Or can I leave the default (rwx/r-x/r-x)

The storage location must allow PHP to read and write within the folder. In most cases, that is 777 permissions but it might be something different if you’re using suExecPHP, etc. 

3 minutes ago, Randy Calvert said:

The storage location must allow PHP to read and write within the folder. In most cases, that is 777 permissions but it might be something different if you’re using suExecPHP, etc. 

Yes, I have a 777.
Do I understand correctly that only the logs folder (775)?

I would just use the same value you use for the parent folder (such as 777).