Well, newspapers are printed on very poor paper, with limited quality applied to ink management - they are just mass produced, with the cheapest possible products.
Starting back with the original scan, what is the resolution at that point - note: for the end product, video, the resolution will be thrown out, and only pixel x pixel dimensions will matter. Still, if one is starting with a high-rez scan, when they manipulate the Image, they are working with the best initial product available.
Next, is this newspaper B/W only, or in color?
If B/W, I would explore doing an Image Adjustment>Threshold in Photoshop, and probably an Unsharp Mask, or Smart Sharpen (but do not over do that).
When done, I would Scale to the size needed, and Save_As a PSD, to be Imported into PrE.
That will probably be as good as it gets.
I have had to "build" newspapers, with artwork that mirrored the masthead, and then the type. Newspaper photographs can be problematic, as what got printed is usually the only accessible image.
Can you link to your scan (maybe on DropBox, or similar), so that we can see what you are starting with.
I have the electronic newspaper on an USB and it is in a good quality, so I dont think it is the problem.
How are you judging the quality of the video? Have you output the file or are you just looking at the playback in the program?
If you're looking at the playback, have you rendered your timeline by pressing Enter?