P2SH-P2WPKH - has always segwit UTXOs?
if I've P2SH-P2WPKH address, does it mean that all outputs to this
  address (UTXOs) are by definition segwit UTXOs ?


Yes, Bitcoin sent to a P2SH-P2WPKH address will produce a segwit UTXO.


  Why they wrote this "For spending of non-segwit UTXO, the signature
  generation algorithm is unchanged" part, what case it covers? If
  you've P2SH-P2WPKH address but you are taking some foreign UTXOs to
  spend(that were directed not to your address)?


I think you're right, it sounds like it's just saying if you want to send to a segwit address, you don't need to sign a non-segwit input any differently than before.

Spending P2SH(P2WPKH)

Here is a good reference example: BIP 141: P2SH(P2WPKH). In order to spend Bitcoin sent to your address 3MxYPuvEcKDdaEG1xoGyddqir6C4b66MJi, you have to provide the following:

witness:      &lt;signature&gt; &lt;pubkey&gt;
scriptSig:    &lt;0 &lt;20-byte-key-hash&gt;&gt;
              (0x160014{389f26d8d616cb96df1cfd6d9989248a30b933b9})


Perhaps you are forgetting the push ops 0x16 and/or 0x14 in scriptSig?