A lot of questions there, I'll respond to one or two of them
What is the difference between MALLOC and PROGMEM and what is actually being stored?
Malloc() is a function that "grabs" a section of SRAM for you, PROGMEM is a macro that forces data to stay in flash memory and not get copied to SRAM.
When you malloc() some SRAM memory you get a pointer to that memory, what you put in there is up to you.
Doesn't saving and retrieving information from the Flash memory take more time?
Yes, but not enough to worry you in this case I think, the LCD is a 1000x slower anyway.
But if you have static data in flash memory why would you need to dynamically allocate SRAM with malloc()? Does the data change at run time?
Rob