Você precisa montar o regex programaticamente. Então ou:
import re
regex = re.compile('^' + re.escape(variable))
items = collection.find({ 'key': regex })
OU
items = collection.find({'key': { '$regex': '^' + re.escape(variable) }})
Observe que o código usa
re.escape
para escapar da string caso ela contenha caracteres especiais. 
