Nokia LCD - random dots at bottom - why?

You are experimenting with the stuff you have laying around, which can be lots of fun.
You're using a PC power supply and a veroboard Arduino.
So recycling is your thing, that's OK.
But you are also using the wires you have available, and apparently because you like to re-use those, you didn't cut them.
That's the most probable cause for your problem.
Those wires are much too long, and now also act as antennae.
They don't only send the data you want to send, they also pick up static and serve that to your display as data to be displayed.

Answer in short:
Don't use wires longer than they absolutely need to be.