According to PayPal documentation when making a payout I can use unencrypted email (EMAIL), unencrypted phone number (PHONE), or encrypted PayPal account number (PAYPAL_ID) to specify a recipient.
How can I get the paypal_id (with a mobile sdk and a server using REST API for example)? Will I get it encrypted and, if not, how should I encrypt it?
You can get it by calling GetTransactionDetails API on an existing transaction. This API gives you the PAYERID, which is a 13 single-byte alphanumeric characters.
https://developer.paypal.com/webapps/developer/docs/classic/api/merchant/GetTransactionDetails_API_Operation_NVP/
There may be some business scenarios that you may want to get the PAYERID from previous transactions. But I agree, EMAIL would be much more straightforward.