but the same payment with the same settings on Android app (4.0.2) has 0.00001968BTC fee!!! The app warns me that that the fee is too high!
Is your Android wallet different than your desktop one? If so then you must have received a few small payments to your Android wallet. Now, all of these
UTXOs need to be combined which increases the weight of the transaction.