Electroneum Paper Wallet

Do I need KYC if I store my ETN coins in the Electroneum paper wallet?

But I do need KYC if I store my ETN coins in the web wallet on the Electroneum web site, correct?

In accordance to the KYC tier stipulations, yes.

When I decided to transfer my ETN from the Electroneum paper wallet to an exchange, will I encounter any restrictions / obstacles if I don’t do KYC?

You need to ask the exchange you are depositing to that.