I have originally posted this as an OpenGl problem and at many points the problem seemed to have been fixed, but it always came back, so I'm starting a new thread.
I installed the calligra-krita package on an x64 Arch. I previously had the version from the Ubuntu repositories and it worked fine.
The problem is only with tablet input (Wacom CTH-480 P&T) and only when OpenGL is turned on. I mostly tested it with basic circle brushes, all have the same amount of lag and no lag when using a mouse or not in OpenGL mode.

I have the Wacom drivers installed. Not having them made no difference, actually.

I'm mostly sure that I have all necessary Nvidia drivers. I could make CUDA renders in Blender, so I guess that should not be a problem.
The GLEW package is also installed. It was missing for a while and installing it really fixed screenshot functionality in VLC and Blender, but nothing in Krita.

When I run Krita from a terminal emulator, I get a lot of these:
Unexpected tool event has come to continuePrimaryAction while being mode 0 !

Check if you didn't accidentally turn on tablet-logging in settings->configure Krita->performance ?

Hmmm. There is no such setting for me. Only performance-logging. And yes I did turn that on to find what is causing these errors.
But even if it caused lag, why does the lag go away if I turn OpenGL off?

Tablet logging is enabled with ctrl-shift-t. But if your standard output is full of debug/warning messages something else is up. Try backing up your kritarc and starting with a clean configuration? For the rest, it's really hard to do remote performance debugging. I've got an nvidia card in my development desktop, proprietary drivers, and never a problem, with windows, kubuntu and opensuse, Cintiq Hybrid Companion or Intuos 3. It's so much easier when things are reproducible