How many nonces on average do I need to try in order to get n leading zeros? Assuming 256-bit hash output, how does the (average) number of nonces I need to try (to solve the proof-of-work puzzle) grow with the number of leading zeroes required, n? Is there a bound on this number?
If you want n zeroes when written in binary, 2n.

If you want n zeroes when written in decimal, 10n

If you want n zeroes when written in hexadecimal, 16n.

If you want n zero bytes, 256n.

However, none of these things are relevant in terms of Bitcoin. The difficulty is not the number of zeroes required; the difficulty is the minimum ratio between a well-defined maximum value, and the hash you got (when interpreted as a 256-bit unsigned integer).

In practice, the formula is that you need difficulty * 248 / 65535 attempts.