Replacing multiple words in a string from different data sets in Python

Essentially I have a python script that loads in a number of files, each file contains a list and these are used to generate strings. For example: "Just been to see $film% in $location%, I'd highly recommend it!" I need to replace the $film% and $location% placeholders with a random element of the array of their respective imported lists.

I'm very new to Python but have picked up most of it quite easily but obviously in Python strings are immutable and so handling this sort of task is different compared to other languages I've used.

Here is the code as it stands, I've tried adding in a while loop but it would still only replace the first instance of a replaceable word and leave the rest.

#!/usr/bin/python
import random

def replaceWord(string):
   #Find Variable Type
   if "url" in string:
       varType = "url"
   elif "film" in string:
       varType = "film"
   elif "food" in string:
       varType = "food"
   elif "location" in string:
       varType = "location"
    elif "tvshow" in string:
        varType = "tvshow"

   #LoadVariableFile
   fileToOpen = "/prototype/default_" + varType + "s.txt"
   var_file = open(fileToOpen, "r")
   var_array = var_file.read().split('\n')

   #Get number of possible variables
   numberOfVariables = len(var_array)

   #ChooseRandomElement
   randomElement = random.randrange(0,numberOfVariables)

   #ReplaceWord
   oldValue = "$" + varType + "%"
   newString = string.replace(oldValue, var_array[randomElement], 1)

   return newString

testString = "Just been to see $film% in $location%, I'd highly recommend it!"
Test = replaceWord(testString)

This would give the following output: Just been to see Harry Potter in $location%, I'd highly recommend it!

I have tried using while loops, counting the number of words to replace in the string etc. however it still only changes the first word. It also needs to be able to replace multiple instances of the same "variable" type in the same string, so if there are two occurrences of $film% in a string it should replace both with a random element from the loaded file.