I believe that this confusion comes from the avoidance of low level details. A function is just a location in memory where instructions are stored. Returning a function is nothing else as returning a pointer to a memory location.

In languages like Java that want to hide everything memory related I also was struggling with grasping what a function really is. Is it even allowed to return a function?

Languages that hide memory locations and direct memory access are one of the reasons that some programmers are struggling with functions returning functions.