Voltage difference between parallel plates of a capacitor

You can add a dielectric b/w the plates in two ways:
(1) Keeping the battery connected
If you keep the battery connected then, as you've written, a constant potential difference would be maintained. The capacitance is given by EA/d( E is the permittivity of the medium b/w plates, A is the plate area, d is the distance between them). On introducing the dielectric E would be increased by a factor of K(dielectric constant). So to satisfy the relation Q= CV, the charge should increase by the same factor. The battery takes care of this by supplying the requisite magnitude of charges to the plates. Remember that a battery's purpose is to maintain a constant potential difference, and it will never change as long as the battery is connected.
(2) After disconnecting the battery
The charge on the capacitor won't change in this case(it's conserved). The potential difference would decrease by a factor of K to satisfy Q = CV. In response to the question you had asked in the comment to BioPhysicist's answer, I think you are forgetting that the electric field is given by Q/EA. Bear in mind that although Q increases K times, so does E. They cancel out and we are left with the same electric field we had before the dielectric was inserted.