You seem to be thinking of using a string, 'store', in order to build a variable name, $store. This gets to the subject of symbolic references, and you do not want to go there.
One way to do what you want is to build a hash that relates such strings to corresponding variables. Then capture the bracketed strings in the sentence and replace them by their hash values
use warnings;
use strict;
my $store = 'Media Markt';
my $time = 'morning';
my %repl = ( store => $store, time => $time );
my $sentence = "I visited [store] in the [time]";
$sentence =~ s/\[ ([^]]+) \]/$repl{$1}/gex;
print "$sentence\n";
This prints the line I visited Media Markt in the morning
The regex captures anything between [ ], by using the negated character class [^]] (any char other than ]), matched one-or-more times (+). Then it replaces that with its value in the hash, using /e to evaluate the replacement side as an expression. Since brackets are matched as well they end up being removed. The /x allows spaces inside, for readibilty.
For each string found in brackets there must be a key-value pair in the hash or you'll get a warning. To account for this, we can provide an alternative
$sentence =~ s{\[ ([^]+) \]}{$repl{$1}//"[$1]"}gex;
The defined-or operator (//) puts back "[$1]" if $repl{$1} returns undef (no key $1 in the hash, or it has undef value). Thus strings which have no hash pairs are unchanged. I changed the delimiters to s{}{} so that // can be used inside.
This does not allow nesting (like [store [name]]), does not handle multiline strings, and has other limitations. But it should work for reasonable cases.