Entiendo que subes los videos a 4k directamente desde la galería sin ningún tipo de edición o compresión. Ya que si YouTube detecta que el video tiene un bitrate bajo es probable que no lo muestre a esa resolución.
A mi es que me suena más a un problema de reproducción del vídeo en los móviles que has probado más que el hecho de que lo suba a 4k o no. Por eso te digo de reproducirlo en un pc mediante un navegador que te permita ver contenido 4k en YouTube.