Actually you could do what you want with the /e modifier (which evals the right hand side before replacement), though you'd need to double it (first for $fill{$key} to be interpreted, then $1). Be careful with that though, if the replacement comes from user input, it means users may execute any code from your perl program.

s/$key/$fill{$key}/ee