Il me paraît que les expressions susmentionnées, sont plus fréquentes que leurs synonymes
C'est possible, je ne sais pas, mais un élément de réponse est que ce ne sont pas exactement des synonymes.
Selon le contexte, on aura tendance à utiliser "mettre en place" ou "installer", par exemple. On dit "installer un programme" sur un ordinateur, pas le "mettre en place". On peut dire qu'une vertèbre s'est "remise en place" après avoir été déplacée, mais dire qu'elle s'est "réinstallée" convient moins bien (la vertèbre n'est pas partout à sa place, il y a une place qui est la bonne place, tandis qu'on peut s'installer n'importe où). Ce sont des exemples extêmes, dans bien des cas la nuance est plus subtile que cela. La question me semble trop vaste pour pouvoir être traitée en détail ici...
Faut-il apprendre la bonne préposition (à, en) par cœur
Pour les trois exemples que vous mentionnez, il me semble que oui. Notez que "mise à jour" comme "tenir à jour" dérivent de "être à jour".
Je ne vois pas tant d'expressions à apprendre que ça avec "mise". Dans "mise sous presse", "mise au rebut" (deux exemples du commentaire de Toto), ou "mettre à la poubelle", la préposition décrit simplement l'action : on met effectivement quelque chose sous la presse ; "au"/"à" indiquent la destination.
implémenter
quemettre en œuvre
, en revanche j'utilise aussi bienmettre à jour
queactualiser
mais c'est sûrement différents dans d'autres domaines