It depends on what exactly your weights apply to.
Let $\mathbf{X}$ be the data matrix with variables in columns and observation in rows. If each observation has an associated weight $w_i$, then it is indeed straightforward to incorporate these weights into PCA: one simply has to multiply each row by the corresponding weight $w_i$ and proceed with the standard PCA (I believe that is what you are referring to, when you mention "weighted covariance matrix"). Note that this is mathematically equivalent to (even though conceptually different from) rescaling the variables (e.g. standardizing them), when one multiplies each column of the data matrix by a certain value.
The paper by Tamuz et al., 2013, that you found, considers a more complicated case when different weights $w_{ij}$ are applied to each element of the data matrix. Then indeed there is no analytical solution and one has to use an iterative method. Note that, as acknowledged by the authors, they reinvented the wheel, as such general weights have certainly been considered before, e.g. in Gabriel and Zamir, 1979, Lower Rank Approximation of Matrices by Least Squares With Any Choice of Weights. This was also discussed here.
As an additional remark: if the weights $w_{ij}$ vary with both variables and observations, but are symmetric, so that $w_{ij}=w_{ji}$, then analytic solution is possible again, see Koren and Carmel, 2004, Robust Linear Dimensionality Reduction.