Where does all the voltage go? 
My understanding of this circuit is that the capacitor must 'use up' all the voltage across the terminals of the battery. 
If you double the distance between the plates, I would assume the voltage drop across the two plates would remain the same as it is still connected to the battery.
However as $$C=\epsilon A/d$$ (for a parallel plate capacitor) the capacitance must decrease. In addition, as $$Q=C\Delta Vc$$ for C to change,  $\Delta Vc$ or $Q$ must also adjust. I would have thought that as the amount of charge is conserved, this would mean that the Voltage must change....
From other answers on this fantastic forum (linked below), I understand that when disconnected the voltage between the plates will intially increase lineary with distance and that (now) makes sense to me, and when disconnected from the battery I understand how the voltage across the plates can change.
But when connected to the battery I am unsure how this works and would appreciate any insight into the matter.   

Why does the voltage increase when capacitor plates are separated?
How is Capacitance affected by a seperation distance and with or without a battery?

 A: The battery supplies a constant voltage, not a constant charge. Your formulas are telling you, correctly, that if you increase the plate separation then the charge on each plate will decrease. 
To explain in a bit more depth, electrochemical cells provide a constant amount of potential difference, because that's how their internal mechanics works, and in the process of charging the capacitor they will provide as much charge as necessary until the capacitor's potential difference matches that of the cell. (Your initial comment, stating that the charge should be constant, makes no sense at all: if you close the circuit, charge will flow continuously.)
Within the capacitor, the potential difference is simply the line integral of the electric field between one plate and the other; since the electric field is homogeneous at strength $E$, the potential difference is given by $\Delta V = E\, d$. If you increase the plate separation $d$, the electric field strength will go down: it has a larger length to act on a prospective test charge, so it can do the same amount of work with a smaller force.
And, finally, the smaller electric field directly implies a smaller charge at the plate, since the surface charge density $\sigma$ is directly related to the discontinuity in the normal component of the electric field:
$$
\sigma = \frac{E_{\perp}^\mathrm{in} - E_{\perp}^\mathrm{out} }{2\epsilon_0}
$$
(where the field outside the capacitor is just zero). The smaller the field, the smaller the surface charge density, and therefore the smaller the total charge.
A: I will try to give a physical picture of what I think happens, hopefully without saying too many bullshits.
So basically, If you apply a voltage V across two separated plates, this will cause charges to build up on each side; that's the idea. 
This happens because of the corresponding electric field E that tends to drive all the elctrons along one direction (the opposite direction of E). This effectively pulls the electrons to one of the plates, while pushing them off the other side. Here, E is the real thing we should focus on to understand (more than V) because it is directly the force that causes the electrons dynamics.
For simplification purposes, let's assume that V linear in the space between the plates, so that we can write the simplified linear relation : E = V/L (I think the assumption of a constant E in 1D empty space is correct anyway, judging from the 1D Maxwell Gauss equation)
So what happens if you increase the distance L, while applying a constant V to your capacitor ? Well, E goes down. Which means your attraction (or push) force to the elctrons is weaker, causing a lesser build-up of the charges across the plates.
So Q does decrease, not V.
I think, by saying "the amount of charge is conserved", you were referring to the local equation of charge conservation. This does not imply that charge never changes anywhere though. It just mean that you can't create it, so if charge density changes, then a current must account for these changes. All conclusion we can draw from this is that, as the charges will decrease on the plates, a bit of current will flow to account for it.
Hope that helped!
A: You title  

Where does all the voltage go?

should be "Where does all the charge go?"  
As the plate separation increases the capacitance of the capacitor $C$ decreases and as the potential difference across the plates $\Delta V_{\rm C}$ is kept constant by the battery the charge stored by the capacitor $Q$ must also decrease.  
$Q\downarrow=C\downarrow \Delta V_{\rm C}$ 
Although it would be electrons which would be moving around the circuit I find it easier to assume that it is positive charges which move around the circuit and the direction in which positive charges move is the direction of the (conventional) current.  
In your diagram the top plate of the capacitor has a surplus of positive charges and the bottom plate has a deficit of positive charge.  
Once the separation of the plates starts to increase positive charge start moving in an anticlockwise direction resulting in the top plate having a decrease in the number of positive charges, ie less positive, and the bottom plate having less of a deficit of positive charges, ie less negative.  
You might find it strange that this movement of positive charge means that positive charge flows into the positive terminal of the battery and out of the negative terminal of the battery.
Work, $V_{\rm C}\Delta Q$, has to be done to moving charge $\Delta Q$ through the battery - compare this to recharging a rechargeable battery.
As the plate separation increases the capacitance of the capacitor decreases and so the energy stored in the capacitor, $\frac 12 C\Delta V^2_{\rm C}$, decreases.
For the whole circuit energy is conserved and 
$$\text{work done separating capacitor plates (one positive and the other negative)} =\\ \text{work done moving charge through battery}+ \text{change in energy stored in capacitor}$$ 
