Обе аббревиатуры корректны.
Слово федеральный в названиях округов пишется с маленькой буквы: Северо-Западный федеральный округ, Южный федеральный округ и др. С большой буквы федеральный пишется как первое слово официального названия: Федеральная служба безопасности РФ, Федеральное агентство по печати и массовым коммуникациям и т. п.
Предложение следует начать с прописной (большой) буквы. Если Вас смущает, что сокращение пишется с прописной буквы, то предложение можно просто перестроить - начать его другими словами.
С прописной буквы пишутся все географические названия, в том числе образные, поэтические, неофициальные, неточные, а также названия стран света в роли наименований разных территорий.
Слова военный округ пишутся строчными буквами.
Если имеется в виду название округа, то корректно с прописной и в кавычках: городской округ «Город Уфа».
Если возникает необходимость написания подобных прилагательных с прописной буквы, то слитное написание меняется на дефисное. Правильно: Северо-Кавказский военный округ. Однако Дальневосточный пишется слитно, т. к. существительное восток не является именем собственным.
Дефис пишется в слове Ханты-Мансийский. Между словами округ и Югра ставится тире (разумеется, с пробелами). Правильно: Ханты-Мансийский автономный округ – Югра.
Правильно: Северо-Западный федеральный округ.
Следует склонять обе части наименования, но только если наименование употребляется без родового слова "округ": возле Юстинианы Примы.
