Let $X$ be a Banach space, $r > 0$, $A: K_r(X) \rightarrow X$ a contraction (where $K_r(X)$ is the closed ball of radius $r$ and center $0$ in $X$), with contraction constant $0<q<1$, which also fulfills $A(S_r(X)) \subseteq K_r(X)$ (where $S_r(X)$ is the boundary of $K_r(X)$).
Then there exists a unique fixed point of $A$ in $K_r(X)$.
There has a question come up concerning my solution of the original question. To answer it would be too much for a comment. I therefore decided to split up the original post.
First Steps
To show uniqueness of the fixed point is simple, since $A$ is a contraction. Assume that $x^*$ and $x^{**}$ are two distinct fixed points of $A$. It then follows that $$ \|x^* - x^{**}\| = \|Ax^* - Ax^{**}\| \leq q\|x^* - x^{**}\| $$ and therefore $q \geq 1$, which is a contradiction.
Before I arrived at the final solution for existence I found two intermediate results.
1) Solution for finite dimensional Banach spaces
Let $X$ be a finite dimensional Banach space. We then define $$ \rho: X \rightarrow K_r(X), \rho(x) = \begin{cases} x &\text{ if } x \in K_r(X)\\ r\frac{x}{\|x\|} &\text{ otherwise} \end{cases} $$ This mapping is also called the radial retraction of $X$ to $K_{r}(X)$ and it is continuous.
Since $A$ is a contraction, $A$ is also continuous. We therefore know that $$ \rho \circ A: K_r(X) \rightarrow K_r(X) $$ is continuous. Since we are in a finite dimensional Banach space the operator $\rho \circ A$ has a fixed point $x^* \in K_r(X)$, which follows from Brouwer's fixed point theorem.
It now remains to show that this is also a fixed point of $A$. Here we will use the second assumption about the boundary. Assume that $\|Ax^*\| > r$. Then $$ x^* = (\rho \circ A)(x^*) = r \frac{Ax^*}{\|Ax^*\|} \in S_r(X) $$ and therefore $Ax^* = \frac{\|Ax^*\|}{r} x^* \not \in K_r(X)$. This is a contradiction to $A(S_r(X)) \subseteq K_r(X)$ and therefore $\|Ax^*\| \leq r$. But then $$ x^* = \rho(Ax^*) = Ax^* $$ and we found a fixed point of $A$.
2) Solution for Hilbertspaces
Following the advice by Daniel Fischer I have succeeded in proving, that $\|\rho(x) - \rho(y)\| \leq \|x-y\|$ holds for all $x,y\in X$ if $X$ is a Hilbertspace. This is quite a lengthy and technical argument involving several cases and the polarisation identity.
Once we know this we can easily see that $\rho \circ A$ is a contraction which maps $K_{r}(X)$ to itself. It therefore has a fixed point by Banach's fixed point theorem and just as in the finite dimensional case we can show that it has to be a fixed point of $A$.
This seemed like a good idea at first, but it is a bit messy and I did not want to pursue it any further. It is also questionable if it works for an arbitrary Banach space. Daniel Fischer assumed that it might work for all uniformly convex spaces but I did not check that.
General Solution
I then got advice to dissect the operator $$ Bx = \frac{x + Ax}{2} $$ which finally led to the
3) Solution for arbitrary Banach spaces
One can see that every fixed point of $B$ is a fixed point of $A$ and for $x, y \in K_{r}(X)$ we have $$ \|Bx - By\| = \|\frac{1}{2}(x - y) + \frac{1}{2}(Ax - Ay)\| \leq \frac{1}{2}\|x - y\| + \frac{1}{2}\|Ax - Ay\| \leq \frac{1 + q}{2}\|x - y\|, $$ so $B$ is a contraction. It remains to show that $B(K_{r}(X)) \subseteq K_{r}(x)$.
If we assume $X \neq \{0\}$ then there always exists $x \in S_{r}(X)$. We then have for $0 \in K_{r}(X)$ that $$ \|A0\| = \|A0 - Ax + Ax\| \leq \|A0 - Ax\| + \|Ax\| \leq q\|x\| + \|Ax\| \leq r(q + 1) \leq 2r. $$ Here I used the fact that $A(S_{r}(X)) \subseteq K_{r}(X)$.
We then get $$ \|B0\| = \left\|\frac{A0}{2}\right\| \leq r $$ as well as for any $0 \neq x \in K_{r}(X)$ $$\begin{align} \|Bx\| &= \left\|\frac{x + Ax - A\left(\frac{r}{\|x\|}x\right) + A\left(\frac{r}{\|x\|}x\right)}{2}\right\| \leq\\ &\leq \frac{1}{2}\|x\| + \frac{1}{2}\left\|Ax - A\left(\frac{r}{\|x\|}x\right)\right\| + \frac{1}{2}\left\|A\left(\frac{r}{\|x\|}x\right) \right\| \leq\\ &\leq \frac{1}{2}\|x\| + \frac{1}{2}q(r - \|x\|) + \frac{1}{2}r =\\ &= \frac{1}{2}\|x\|(1 - q) + \frac{1}{2}qr + \frac{1}{2}r \leq\\ &\leq \frac{1}{2}r(1 - q) + \frac{1}{2}qr + \frac{1}{2}r = r \end{align} $$
Finally we get $B(K_{r}(X)) \subseteq K_{r}(X)$ and by Banach's theorem we now know that $B$ has a fixed point which is also a fixed point of $A$.
Heuristics
I was asked by Chellapillai how I arrived at the idea of dissecting the map $$ Bx = \frac{x + Ax}{2}. $$ As said above is this no idea of my own but I also tried to come up with a heuristic afterwards.
It is quite simple to show that $A$ must map $K_{r}(X)$ to $K_{2r}(X)$ (this works quite similar to the case $x = 0$ above. Just use $r\frac{x}{\|x\|}$ instead of arbitrary $x \in S_{r}(X)$.) It is therefore simple to arrive at the idea of dissecting the operator $$ Bx = \frac{1}{2}Ax. $$ This is obviously a contraction if $A$ is a contraction and it maps $K_{r}(X)$ back to itself. By Banach's theorem it therefore has a fixed a point and therefore must hold that $$ x^{*} = Bx^{*} = \frac{1}{2}Ax^{*} \Leftrightarrow Ax^{*} = 2x^{*}. $$ This far I did get before getting advice but I thought it would not lead anywhere. But from there it is actually quite simple to arrive at the right operator. Just look at $$ \begin{align*} &Ax^{*} = x^{*} + x^{*}\tag{1}\\ &Ax^{*} + x^{*} = x^{*} + x^{*} \Leftrightarrow\tag{2}\\ &\frac{Ax^{*} + x^{*}}{2} = x^{*} \end{align*} $$