Приложение — это компонент, главная функция которого состоит в дополнительной характеристике определяемого слова. Эта дополнительная характеристика может носить уточняющий характер, может служить указанием на особую важность предмета в каком-либо отношении (старейшая газета России в Вашем примере), может называть классифицирующий признак предмета (летопись в Вашем примере) и др. Поэтому ориентироваться разумнее не на различные попытки вывести правила разграничения приложений и определяемых слов, которые содержатся в различных пособиях, но не охватывают и не могут охватить всего разнообразия смысловых и прочих отношений в конструкциях с приложениями, а на этот главный признак: то, что служит дополнительной характеристикой, и является приложением.

Как Вы уже поняли, никаких реальных ограничений на то, чтобы главное слово было собственным наименованием в кавычках, не существует. Безусловно, бывает, что такое название как раз и служит приложением (кафе «Березка»), но из этого нельзя выводить никакого правила.

Когда имеется обособление, решать, конечно, проще: в обоих Ваших примерах обособленные компоненты и являются приложениями.
 

Корректно согласование со словом "один": мне исполнился 31 год, мне был 31 год.

Верно: на 71 из 99 столов, на 71 столе из 99.

Грамматически верно: В объёме 21 (двадцати одной) единицы (штуки, тонны). 

Запятые не нужны, нет оснований для обособления. 

Корректно: В 2001 году количество товаров было уменьшено до 76, а в дальнейшей перспективе будет поддерживаться на уровне 71 единицы.

Корректно: представление документов приложением к заявлению.

Это (написание в три слова) правильно, поскольку соединяются слова, записанные в разных алфавитных системах.

В первом случае даны две разные падежные формы одного и того же существительного в сочетании с разными количественными числительными — для точности и полноты ответа на заданный вопрос. Во втором случае существительное не повторено — это распространенный вариант записи интервалов, диапазонов и прочих промежуточных отрезков.

Предпочтительнее все сказуемые, относящиеся к сочетанию 20 человек, поставить в форму мн. числа: прибегут 20 человек и замучают, накормят, напоят и предложат.

Подробнее о правилах, определяющих выбор числа сказуемого, см. в «Письмовнике».