Before Mathematica used the rule, it evaluated the right hand side. Evaluating the rule by itself shows what happened:
In[60]:= {x_, y_} -> {x, Log[2, y]}
Out[60]= {x_, y_} -> {x, Log[y]/Log[2]}
The two argument form of Log evaluates to a ratio of natural logs unless both arguments are numeric. Then, when it substituted 4 for y, it preserved that form. Mathematica will not automatically recognize that it can simplfy the ratio of logarithms.
FullSimplify can simplify this. However, it's probably better to delay the evaluation. In this case, you could use RuleDelayed:
In[59]:= Replace[{{1, 2}, {3, 4}}, {x_, y_} :> {x, Log[2, y]}, 1]
Out[59]= {{1, 1}, {3, 2}}
Another way would be to define your own function for numeric arguments only:
In[56]:= log2[x_ /; NumberQ[x]] := Log[2, x]
In[58]:= Replace[{{1, 2}, {3, 4}}, {x_, y_} -> {x, log2[y]}, 1]
Out[58]= {{1, 1}, {3, 2}}
