A very interesting idea ...
If you are new to all this stuff you need to make your project absolutely as simple as possible.
As @groundfungus has said, stepper motors should provide the motion and the position-keeping all in one. I think you will need to use narrow hard wheels with very thing tires to minimize slip between the wheels and the surface.
Don't bother with the complication of encoders until you are sure that you need them - i.e. after you have a project that works reasonably well but "could do better".
A small servo can be used to lift and lower the pen. I suggest the pen should be held on the paper by weight and be free to move up and down a few mm rather than being held down firmly by the servo.
It might also be a good idea to start without bothering with batteries. It shouldn't be a problem for the robot to drag a cable around if you hold the cable to minimize drag - at least for the initial testing stage. It will also allow for the Arduino code to be updated quickly.
MOST IMPORTANT the motors (whatever sort you choose) and servo need to be powered separately from the Arduino. The Arduino can't provide enough current for motors.
...R