Conceptual Understanding of Zero Curl in Ampere's Law I understand that Ampere's law tells us that the current density times $\mu_0$ at some location must be equal to the curl of $\mathbf{B}$ at that location. However, conceptually this is troubling me. 
In particular, in my mind I am imagining a long wire with some current density $J$ running through it. Then out side this wire, $B$ should be proportional to $s^{-1}$, where $s$ is the distance from the wire (the integral of $\mathbf{B}$ over any loop around the wire should, however, be $\mu_0$ times I enclosed). At all locations outside the wire $J$ is zero, so $\text{curl}(\mathbf{B})$ must also be zero. 
$\text{curl} = 0$ at some point implies that placing a paddle wheel at that point won't cause the paddle wheel to turn. However, let's look at a cross section of the wire with the $B$ field spinning around it. Then if we place a paddle wheel (+ shaped) at the 12 o clock point in the configuration, the bottom part of the wheel should be pushed on harder than the top part (since $B$ falls off with $s$ and the top is farther from the wire than the bottom). 
So there SHOULD be a curl, or at least that's what I would reason without the mathematics. But since the maths isn't wrong, where is my reasoning wrong?
 A: Your reasoning is wrong because you are fixing the wheel in space. Of course it is going to spin. If we abstract the field as flow lines, the $1/s$ circular flow is irrotational, but the paddle wheel needs to move with the fluid for that to work.
The imaginary paddle wheel is now orbiting at some distance $s$ from the center. It central field is:
$$ B_0 = \frac 1 s$$
while the top and bottom paddles feel
$$ B_{\pm} = \frac 1 {s \pm ds} = B_0( 1 \mp ds)$$
so in the rotating frame moving at $B_0$ it rotates backwards at exactly the rate of revolution, leaving it irrotational in the fixed frame.
A: For a very long, thin wire along the z-axis with current $I$, the magnetic field is given in cylindrical coordinates $(\rho,\phi,z)$ by
$$\mathbf B=\frac{\mu_0I}{2\pi\rho}\hat\phi$$
Let's calculate the curl of this field. In cylindrical coordinates the curl of a vector field with only a $\phi$ component is given by
$$\nabla\times\mathbf B=-\frac{\partial B_\phi}{\partial z}\hat \rho+\frac{1}{\rho}\left(\frac{\partial}{\partial \rho}(\rho B_\phi)\right)\hat z$$
Given that $B_\phi=\frac{\mu_0I}{2\pi\rho}$, we have
$$\frac{\partial B_\phi}{\partial z}=0$$
$$\frac{\partial}{\partial \rho}(\rho B_\phi)=0$$
Therefore, we have $\nabla\times\mathbf B=0$ at all points in space except where $\rho=0$ where the $1/\rho$ part gives us some trouble. However, you can do some tricky math to show that the curl on the z-axis results in a Dirac Delta distribution, so we end up with
$$\nabla\times\mathbf B=\frac{\mu_0I}{2\pi\rho}\delta(\rho)\hat z=\mu_0\mathbf J$$
as expected. So everything works out fine.

$\text{curl} = 0$ at some point implies that placing a paddle wheel at that point won't cause the paddle wheel to turn. However, let's look at a cross section of the wire with the $B$ field spinning around it. Then if we place a paddle wheel (+ shaped) at the 12 o clock point in the configuration, the bottom part of the wheel should be pushed on harder than the top part (since $B$ falls off with $s$ and the top is farther from the wire than the bottom). So there SHOULD be a curl, or at least that's what I would reason without the mathematics. But since the maths isn't wrong, where is my reasoning wrong?

Your paddle wheel needs to be infinitely small. You could put a similar paddle wheel in certain charge distributions for the electric field and get them to spin when we know the curl of the electrostatic field must always be $0$. The issue is that the curl is a deferential operator that works with infinitesimal quantities. Therefore, you need to think in terms of an infinitesimal paddle wheel. Then you will see that you don't get any spinning at points not on the z-axis.
A: According to my understanding divergence and curls are to be taken at a point in space, (just like we take derivative of a function at a point). Loosely speaking, we can call them as point operations. Differential form of Amperes law says, wherever the source exist ( current density) then curl of B exist. You can verify this. But source of current can produce magnetic field  outside the region of current density also (Biot-Savart Law). Don't forget we derived Amperes law using Biot-Savart Law. 
A: 
Then if we place a paddle wheel (+ shaped) at the 12 o clock point in the configuration, the bottom part of the wheel should be pushed on harder than the top part (since B falls  off with s and the top is farther from the wire than the bottom).

To the OP: This bothered me for quite some time, so I sympathize with you.
You show a + shaped paddle wheel with four vanes. You are right the bottom part of the wheel would be pushed harder than the top part. Your intuition is having a problem here because unknowingly it is ignoring the other two vanes of the paddle to the left and right. If the bottom vane is getting pushed toward an anti-clockwise rotation, the other three are getting pushed toward a clockwise rotation, not just the top one. Try drawing the + shaped paddle wheel on top of the circular field.
Now, it is amazing that with a B field that falls of as 1/distance, the bottom vane gets exactly balanced by the other three vanes! (Intuition satisfied, I trust to the math that it will work out)
One can question why a paddle wheel with four vanes... but I think it should be possible to show that any other configuration of vanes is equivalent to the four vane wheel.
PS: This is called a curl-free macroscopic circulation over here:
https://mathinsight.org/curl_subtleties#curlfreecirc
