Let the total number of votes before Paul voted be $n$, and the number of votes for $A$ before Paul voted be $k$. The percentage of votes for $A$ before Paul voted is $\frac{100k}{n}$, which is a positive integer. After Paul votes for $A$, the number of votes for $A$ becomes $k+1$, and the total number of votes becomes $n+1$. The new percentage is $\frac{100(k+1)}{n+1}$. We are told that this new percentage is exactly one more than the previous percentage:

$$\frac{100(k+1)}{n+1} = \frac{100k}{n} + 1$$

Let $p = \frac{100k}{n}$, so $k = \frac{pn}{100}$.

Substitute $k$ into the equation:

$$\frac{100\left(\frac{pn}{100} + 1\right)}{n+1} = p + 1$$

Multiply both sides by $n+1$:

$$100\left(\frac{pn}{100} + 1\right) = (p + 1)(n + 1)$$

$$pn + 100 = pn + p + n + 1$$

$$100 = p + n + 1$$

$$p + n = 99$$

Recall that $k = \frac{pn}{100}$ must be an integer, and $p$ and $n$ are positive integers with $p + n = 99$.

Let $n = 99 - p$.

Then:

$$k = \frac{p(99 - p)}{100}$$

We need $k$ to be an integer, so $p(99 - p)$ is divisible by $100$.

Let us try all $p$ from $1$ to $98$ (since $p$ and $n$ are positive integers):

We seek $p$ such that $p(99 - p)$ is divisible by $100$.

Let us try $p = 19$:

$19(99 - 19) = 19 \times 80 = 1520$, and $1520/100 = 15.2$ (not integer).

Try $p = 80$:

$80(99 - 80) = 80 \times 19 = 1520$, $1520/100 = 15.2$ (not integer).

Try $p = 20$:

$20 \times 79 = 1580$, $1580/100 = 15.8$ (not integer).

Try $p = 25$:

$25 \times 74 = 1850$, $1850/100 = 18.5$ (not integer).

Try $p = 50$:

$50 \times 49 = 2450$, $2450/100 = 24.5$ (not integer).

Try $p = 4$:

$4 \times 95 = 380$, $380/100 = 3.8$ (not integer).

Try $p = 75$:

$75 \times 24 = 1800$, $1800/100 = 18$ (integer!).

So $p = 75$, $n = 24$, $k = 18$.

Check: Before Paul voted, $n = 24$, $k = 18$, so percentage is $\frac{100 \times 18}{24} = 75$.

After Paul votes for $A$, $k = 19$, $n = 25$, percentage is $\frac{100 \times 19}{25} = 76$.

So the percentage increases by exactly $1$.

Therefore, Paul's vote was the nineteenth vote for option $A$.