Do I need KYC if I store my ETN coins in the Electroneum paper wallet?
No, you don’t need KYC if you use 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.