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

Корректно: заповедник «Три столба», «Томские стоянки».

Выделять имя знаками препинания не требуется. Вызывает сомнение только начало предложения: «Сейчас бывший чемпион...» Если есть возможность, слово «сейчас» лучше убрать.

Корректно: Джей Дабл-ю.

Возможно: Уважаемый господин Ким!

Инициалы – это графические сокращения имени и отчества. Графическое сокращение означает, что при прочтении слово читается полностью: мы не читаем [и-и-иванов], мы говорим либо просто Иванов, либо Иван Иванович Иванов.

В живой речи имя и отчество практически всегда предшествует фамилии (исключение – бюрократическая, канцелярская речь). Хорошая традиция – перенести этот принцип и в письменную речь.

Естественно, исключением останутся пофамильные алфавитные перечни, в которых фамилия играет организующую роль и предшествует инициалам.

К сожалению, мы не можем дать совет по делопроизводству - указывать номер телефона или нет. Что же касается пробелов, то они ставятся как между фамилией и инициалами, так и между инициалами имени и отчества.

Можно верить рекомендациям справочника Д. Э. Розенталя (нормативны конструкции: с целью осуществить – в целях осуществления). Но при этом нет прямого запрета на использование варианта "с целью осуществления".

Такая конструкция в меньшей степени соответствует речевой практике, хотя и в ней тоже встречается, например: Подкуп свидетеля, потерпевшего в целях дачи ими ложных показаний либо эксперта, специалиста в целях дачи ими ложного заключения или ложных показаний, а равно переводчика с целью осуществления им неправильного перевода [Уголовный кодекс Российской Федерации].

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

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

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

После слов как вариант нужно поставить запятую или двоеточие.