Str replace should work for most cases:
foreach($variables as $key_l1 => $value_l1)
foreach($value_l1 as $key_l2 => $value_l2)
$string = str_replace('%'.$key_l1.':'.$key_l2.'%', $value_l2, $string);
Eval forks a new PHP process which is resource intensive -- so unless you've got some serious work cut out for eval it's going to slow you down.
Besides the speed issue, evals can also be exploited if the origin of the code comes from the public users.