Вот я приехал, арендовал квартиру - мне нужно в УФМС сообщить, где я проживаю
Не вы должны сообщить, а собственник (один из собственников). Называется уведомление о прибытии иностранного гражданина. Формально вы никаким боком эту бумажку не заполняете. Её заполняет и сдает собственник со своим и вашим паспортом.
получить регистрацию по месту жительства
Регистрацию вроде делают только после РВП, или патента или трудового договора...
предоставить документ на право ПОЛЬЗОВАНИЯ жилым помещением (это договор аренды)
Да от всех собственников. Нужно их присутствие. Если кого-то нет, можно нотариальное согласие или доверенность.
Лучше перед отъездом из Казахстана подайте на программу переселения.
Потом прилететь за свидетельством будет дешевле, чем платить за ВНЖ, за экзамены, за регистрацию.
И быстрее, чем ждать начала года для квоты РВП (в лучшем случае начала 2016-го, а то и 2017) и потом еще ВНЖ.