Character sums concerning $a^x-1$

The best result on the market is the one of Yu, who proves that your sum is less than $$p^{1/2} \left( \frac 2 \pi \log p + \frac 7 5 \right).$$ If $a$ is not a primitive root there is an adjustment by a factor which depends on the index of $a$. Also see Dobrowolski&Williams for essentially the same bound in the special case of Legendre symbols. Yu also proves the same bound for prime power moduli. See moreover Shparlinski for non-primitive characters, where there is an extra factor depending on the conductor of $\chi$; again from Yu, the displayed bound is in this case best possible up to a $\log q$ factor. Shparlinski and others comment that much less is studied for this kind of sums, involving multiplicative characters, than for the analogues with additive characters, especially for short sums.

Shparlinski has done a lot of work on problems like this, in the more general setting of linear recurrence sequences. (Your sequence of Mersenne numbers is such a sequence).

I'd recommend looking at Chapter 5 of

Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward - Recurrence Sequences

and the references therein (see e.g. p 86).