Scaling video lowers quality in Premiere Pro
Why this is happening: because an interpolation method the Premiere uses for scaling kills high frequency details (ie., sharp edges, as text or some thin elements of the GUI are).

A scaling interpolation method (in our case, Lanczos method, as an Adobe employee mentions here) is an algorithm used to map an array of pixels of one size into an array of a different size. You have a 200x200 image and want it to be 400x400. What do you do? Quadruple each pixel of an original image so it will take 4 pixels in an upscaled image? Or blend the neighboring ones somehow?

There are a couple of algorithms developed, like Nearest Neighbor, Bilinear, Bicubic and Lanczos. They differ in computational complexity and in the quality of the results they produce. And the quality (here we finally come to your question) also depends of the nature of the source material. Adobe chose Lanczos because it does a decent job at scaling natural images taken by camera. If this was an image of a person, you would expect that a scaled down version will not have the individual hairs and the little marks on the skin to be seen in the same detail as they are seen on an original larger image.

Yet, you are scaling down a different kind of footage – the screen capture of a software GUI. The one you'd want to see all the sharp details even on a scaled down image. As you see, the Lanczos method does a bad job here.

And we come your second question: what algorithm would do a better job, or how to fix this?

Short answer: in Premiere, you can't.
Long answer: a scaling algorithm we need is a Nearest Neighbor algorithm. This one preserves the sharp edges of the GUI just as we like it. Adobe After Effects has it (called "Draft" scaling quality). Premiere doesn't (natively). You can try your luck searching for "Nearest Neighbor scaling plugin" for Premiere.