The main problem I see to PBOs for sprite images is that the GPU will be too busy for shaders, right?
The GPU is usually idle, waiting for the CPU to complete all the driver calls made by SFML. Even if you use shaders.
I think the biggest bottleneck for me right now is LoadPixels and SubRect.
You should profile your code before optimizing anything. By the way, what are you doing? How do you use LoadFromPixels? Why do you think that SetSubRect is a bottleneck (internally it doesn't do anything except assigning the rect)?
I already need to replace GetPixel and SetPixel for speed.
For speed you should never use them, and rather work on your own array of pixels, then use LoadFromPixels (or UpdatePixels in SFML 2).