Это происходит потому что в трекере изменений EF нет информации о Country в момент сохранения.
Вам нужно "присоединить" существующие страны к контексту перед сохранением. Вот пример в официальных доках
Наверное самое простое - это перейти на https, чтобы нельзя было легко "подсмотреть" запросы.
Если немного усложнить - то можно применить SSL Pinning, чтобы усложнить процесс подглядывания.
Еще несложный вариант - "подписывать" запросы - добавлять параметр sign=.... где ... это будет например md5 от "секретная строка" + параметры запроса (потребуется уже декомпилировать приложение).