Partly following the advise in Anton Petrunin's answer, let me present a proof in greater detail.
We prove the statement in the case of non-negative curvature. Assume the contrary. Then there exist $\delta >0$ and sequences $x_n,y_n\to p$ such that $0<|px_n|\leq |py_n|\to 0$, and
\begin{eqnarray}\label{0}
\tilde\measuredangle x_npy_n< \measuredangle x_npy_n-\delta.
\end{eqnarray}
We denote for brevity
$$r_n:=|px_n|,\, R_n:=|py_n|,\, \alpha_n:=\measuredangle x_npy_n, \tilde\alpha:=\tilde\measuredangle x_npy_n.$$
Thus
$$r_n\leq R_n\to 0,\, \tilde\alpha_n<\alpha_n-\delta.$$
Choosing a subsequence, we may assume that there exists a geodesic $\gamma$ starting at $p$ such that the angle between its direction at $p$ and the direction of $px_n$ is at most a small $\omega$ to be chosen later.
Let $z_n\in \gamma$ be such that $|pz_n|=r_n$.
We have
\begin{eqnarray}\label{1}
|x_nz_n|=\sqrt{2r_n^2(1-\cos\tilde\measuredangle x_npz_n)}=2r_n \sin{(\frac{\tilde\measuredangle x_npz_n}{2})}\leq r_n\cdot \omega.
\end{eqnarray}
Let us show that the angles $\tilde \measuredangle z_npy_n$ and $\tilde \measuredangle x_npy_n$ are very close to each other. We have
\begin{eqnarray*}
|x_ny_n|^2=r_n^2+R_n^2-2r_nR_n\cos\tilde\measuredangle x_npy_n,\\
|z_ny_n|^2=r_n^2+R_n^2-2r_nR_n\cos\tilde\measuredangle z_npy_n.
\end{eqnarray*}
Subtracting the two equalities we get
\begin{eqnarray*}
2r_nR_n(\cos\tilde\measuredangle z_npy_n-\cos\tilde\measuredangle x_npy_n)=(|z_ny_n|-|x_ny_n|)(|z_ny_n|+|x_ny_n|).
\end{eqnarray*}
This and (\ref{1}) imply
\begin{eqnarray*}
|\cos\tilde\measuredangle z_npy_n-\cos\tilde\measuredangle x_npy_n|\leq \omega \frac{|z_ny_n|+|x_ny_n|}{2R_n}\leq \omega \frac{r_n+R_n}{R_n}\leq 2\omega.
\end{eqnarray*}
Since $|\arccos a-\arccos b|\leq C|a-b|^{1/2}$ for some fixed $C\geq 1$ and any $a,b\in [0,\pi]$, we obtain
\begin{eqnarray}\label{2}
|\tilde\measuredangle z_npy_n-\tilde\alpha_n|\leq C\sqrt{2\omega}.
\end{eqnarray}
On the other hand
\begin{eqnarray*}
\measuredangle z_npy_n-\tilde\measuredangle z_npy_n\geq (\measuredangle x_npy_n-\measuredangle z_npx_n)-(\tilde\alpha_n+C\sqrt{2\omega})\geq\\
\measuredangle x_npy_n-\tilde\alpha_n-(\omega+C\sqrt{2\omega})\geq \delta -(\omega+C\sqrt{2\omega}).
\end{eqnarray*}
Now let us choose $\omega$ so that $\omega+C\sqrt{2\omega}<\delta/2$. Then we get
\begin{eqnarray}\label{3}
\measuredangle z_npy_n-\tilde\measuredangle z_npy_n> \delta/2.
\end{eqnarray}
Thus we reduced the problem to the case when the points $z_n$ lie on the same geodesic $\gamma$ and $|pz_n\leq |py_n|$. Now choose point $w_n\in \gamma$ such that $|pw_n|=|py_n|$.
We have $\tilde\measuredangle w_npy_n\leq \tilde\measuredangle z_npy_n$. Hence by (\ref{3}) we have
\begin{eqnarray}\label{4}
\measuredangle w_npy_n-\tilde\measuredangle w_npy_n> \delta/2.
\end{eqnarray}
Thus now $|pw_n|=|py_n|$. Like in the previous step we can find another geodesic $\hat\gamma$ such that its direction at $p$ is very close to the directions at $p$ of the geodesics $py_n$.
We choose points $t_n\in \hat \gamma$ such that $|pt_n|=|py_n|$. Repeating the argument as above we get for $n\gg 1$
$$\measuredangle w_npt_n-\tilde\measuredangle w_npt_n> \delta/4.$$
But $\measuredangle w_npt_n$ equals the angle between $\gamma$ and $\hat\gamma$, and $\tilde\measuredangle w_npt_n$ converges to this angle by definition. This is a contradiction. QED
