Another answer already gives a reference to a smaller exponent, but since the OP states that they are interested in an elementary proof, this is a proof I came up with which shows $c < \frac{3}{7} + \varepsilon$ (which is smaller than $\frac{4}{9}$).
For $A \subset \left( \mathbb{Z} / p \mathbb{Z} \right)^{*}$ we define $A A = \left\{ xy : x, y \in A \right\} \subset \mathbb{Z} / p \mathbb{Z}$ and $r (a) = \# \left\{ xy \equiv a : x, y \in A \right\}$, where throughout we will let $\equiv$ denote equality $\bmod p$ (just to simplify writing). We define the multiplicative energy of $A$ to be $E(A) = \# \left\{ x, y, z, w \in A : xy \equiv zw \right\}$. Notice that $$\sum_{x \in A A} 1 = \lvert A A \rvert$$ $$\sum_{x \in A A} r(x) = \lvert A \rvert^2$$ $$\sum_{x \in A A} r(x)^2 = E(A)$$ and so by Cauchy-Schwarz, $\lvert A \rvert^4 \leq \lvert A A \rvert E(A)$.
As stated in the post, it is sufficient to show $\lvert A_d \rvert \leq p^{3/8 + \varepsilon}$. Our strategy will be to bound $\lvert A_d A_d \rvert$ and $E(A)$. Notice that since every element of $A_d$ is a $d$-th root of unity, so is every element of $A_d A_d$, and therefore $\lvert A_d A_d \rvert \leq d$. Also, every element of $A_d$ is of the form $d x$, where $x < \frac{p}{d}$. This means that the multiplicative energy of $A_d$ is at most $$\# \left\{ x, y, z, w < \frac{p}{d} : xy \equiv zw \right\}$$ We split into cases according to the larger among $d$ and $\sqrt{p}$.
Case 1: $d > \sqrt{p}$. In this case, $xy \equiv zw$ is equivalent to $xy = zw$. Fixing $x, y$, the number of solutions is at most the number of divisors of $xy$, which is $\ll p^{\varepsilon}$, and so $E(A_d) \ll \frac{p^{2 + \varepsilon}}{d^2}$. This means that $$\lvert A_d \rvert \ll \left( d \cdot \frac{p^{2 + \varepsilon}}{d^2} \right)^{1/4} \ll p^{3/8 + \varepsilon}$$ which is even stronger than what we require.
Case 2: $d < \sqrt{p}$. Now, $xy \equiv zw$ means that $xy + pk = zw$ for some $k \leq \frac{p}{d^2}$. Fixing $x, y, k$ we have as before $\ll p^{\varepsilon}$ solutions, and so the multiplicative energy is at most $$\frac{p^{3 + \varepsilon}}{d^4}$$ which as before gives that $$\lvert A_d \rvert \ll \left( \frac{p}{d} \right)^{3/4 + \varepsilon}$$ This bound is relatively good for $d \approx \sqrt{p}$, however when $d$ is small this is quite bad. Luckily, we always have the trivial bound $\lvert A_d \rvert \leq d$. Optimizing, we get that $\lvert A_d \rvert \ll p^{3/7 + \varepsilon}$, as required.