I like premature returns and think they reduce complexity, but as exclipy writes (I think quoting Ousterhout) 'complexity is defined as "how difficult is it to make changes to it"'.
If premature returns are the only premature exit your language has then they add complexity in that you can't then add code (in just one place) that is always executed before returning.
A good language will also have "break" from any block of code, such that the break can also carry a return value, AND the break can be from any number of nested blocks, which would generally mean that blocks can be labelled / named. And also of course that any block can have a return value.
So you don't actually need a distinguished "return" but only a "break" that can be from the main block of the function.
A nice way to do this is the "exit function", especially if the exit function is a first class value and can also exit from called functions. (of course they need to be in a nested scope or have the exit function passed to them somehow).
It is also nice to allow each block to have a "cleanup" section, so that adding an action to happen on every exit doesn't require wrapping the block in another block, but this is just a convenience, not a necessity.
Note that this is quite different to exception handling try / catch / finally (Java terms) though it can be used to implement exception handling.