I believe if a level seems like it can be beat, but the player fails due to their own lack of knowledge or skill, then it can be considered challenging and fun. The player knows that if they learn that skill or knowledge then they can beat the level.
On the other hand, if the player feels that their inability to complete the level is due to forces outside of their control, like random death or knowledge that is not generally available or available within the context of the game, then they will get frustrated and the game won't be fun.
So, in my opinion, what makes a game fun is not as much about the level of difficulty, but is more about giving the player the feeling that they can beat the game if they can just improve their own skills or use/expand their own knowledge, no matter the difficulty.
One personal example that comes to mind is —'s The Convergence. There wasn't much help at the beginning, and it took a while to figure out what to do, but everytime I failed, I knew it was my fault and that it was possible to beat. If there had been randomly appearing wormholes that killed me, or I needed to know how to calculate the integral of a multi-variable function, then I would have angrily stopped playing.
The key is to make the player feel like they are in control and that they have everything they need at hand to beat the game.