NDSolve is full of mysteries. I learnt that sometimes forcing something to be zero for a (very) short time can help.
You could try this.
h = 13/(1000^2);(*units are converted to mm*)k = 0.3/1000;
c = 1030;
rou = 1380/(1000^3);
heq = rou*c*D[u[t, x], t] == k*D[u[t, x], {x, 2}];
ic = u[0, x] == 275;
bcs1 = (D[u[t, x], x] /. x -> 5) == -h*(u[t, 5] - 25) (1 - Exp[-30 t]);
bcs2 = (D[u[t, x], x] /. x -> -5) ==
h*(u[t, -5] - 25) (1 - Exp[-30 t]);
sol = NDSolve[{heq, ic, bcs1, bcs2}, u[t, x], {t, 0, 20}, {x, -5, 5},
Method -> {"MethodOfLines",
"SpatialDiscretization" -> {"TensorProductGrid",
"MinPoints" -> 100}}];
F[t_, x_] = u[t, x] /. sol[[1]];
Plot3D[F[t, x], {x, -5, 5}, {t, 0, 15}, PlotRange -> All,
AxesLabel -> Automatic]