"This movie was very interesting."
Your answer is correct. です can be used after かった and it would be more polite as Rhiaaaaannon said. かった is showing that it is past tense.
When the です is missing it means the sentence is casual. We would speak that way with people we know well (friends & family), but not with your boss.
You could also say 「とても面白い映画でした」when you were talking if you wanted to use the past tense form of です. This sentence would work because the noun came before the でした.
If you're talking about a story, you usually say おもしろい to mean interesting.