Необходимость постановки тире зависит от того, как прочитывается сочетание 13 июля. Если подразумевается форма именительного падежа, то оно играет роль подлежащего. Соответственно, сочетание день рождения будет выполнять функцию сказуемого, а между подлежащим и сказуемым-существительным ставится тире: День рождения Андрея — тринадцатое июля. Если подразумевается форма родительного падежа, то сочетание играет роль обстоятельства времени, что не предполагает постановки знаков препинания: День рождения Андрея тринадцатого июля. При этом может быть использовано интонационное тире для указания места распадения простого предложения на словесные группы: День рождения Андрея — тринадцатого июля.

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

Форма множественного числа сказуемого показывает, что в роли подлежащего выступает все сочетание, т. е. действие приписывается двум взаимосвязанным равноправным субъектам, например: После обеда Лось с Русаковым пошли посмотреть склады и магазины (Т. Семушкин); Встали и Воропаев с Корытовым (П. Павленко).

Форма единственного числа сказуемого показывает, что подлежащим является только существительное в именительном падеже, а существительное в творительном падеже выступает в роли дополнения, обозначая лицо, сопутствующее производителю действия, например: Граф Илья Андреевич в конце января с Наташей и Соней приехал в Москву (Л. Толстой); ...Пришел Разметнов с Демкой Ушаковым (Шолохов).

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

В других случаях играет роль лексическое значение сказуемого, например: Мать с дочерью долго не могли успокоиться и вспоминали случившееся (оба действия могут производиться при равноправном участии субъектов действия); Коля с Петей поступили в одну и ту же школу; Брат с сестрой возвратились порознь. Ср.: Клычков с Чапаевым разъехались по флангам... (Фурманов).

Иногда играет роль порядок слов в сочетании. Ср.: Муж с женой пошли в театр. – Жена с мужем пошла в театр (обычно в рассматриваемых конструкциях при различной родовой принадлежности существительных на первом месте фигурирует более сильный в грамматическом отношении мужской род, например: отец с матерью, дед с бабкой, мальчик с девочкой; поэтому выдвижение на первое место существительного в форме женского рода подчеркивает его роль, а отсюда согласование с ним сказуемого).

Полное прилагательное типа бескрайний, конечно, может играть роль сказуемого; для полного действительного причастия типа холодящий эта роль гораздо менее естественна, сравним: *Звёзды холодящие до дрожи — Звёзды холодят до дрожи (здесь явно предпочтителен второй вариант, со спрягаемой формой глагола). Вместе с тем оба приведенных Вами предложения будут в полной мере соответствовать нормам русской грамматики, если считать, что это номинативные (назывные) предложения — односоставные предложения с главным членом-подлежащим, в которых сообщается о существовании и наличии предмета. В данном случае они содержат распространители — согласованные распространенные определения, находящиеся после определяемого слова. Такие распространители выделяются запятыми: Одиночество, бескрайнее, как степи, Звёзды, холодящие до дрожи.

Слова может, может быть выделяются как вводные в значении 'вероятно, возможно': Шаганэ ты моя, Шаганэ! Там, на севере, девушка тоже, На тебя она страшно похожа, Может, думает обо мне...(Есенин) И когда с другим по переулку Ты пойдешь, болтая про любовь, Может быть, я выйду на прогулку, И с тобою встретимся мы вновь (Есенин).

Запятые не ставятся, если слова может, может быть употребляются в значении сказуемого: Было душно от жгучего света, А взгляды его – как лучи. Я только вздрогнула: этот Может меня приручить (Ахматова). Была чудная ночь, такая ночь, которая разве только и может быть тогда, когда мы молоды, любезный читатель (Достоевский).

В справочниках наблюдаются разногласия относительно пунктуационного оформления слова значит в тех случаях, когда оно соединяет части сложного предложения. Так, в справочнике по пунктуации Д. Э. Розенталя читаем:

«Если слово значит находится между придаточной и главной частями сложноподчиненного предложения, то оно выделяется запятыми: Если наступит весна, значит, будет тепло; Раз так упорно отстаивает свои взгляды, значит, чувствует свою правоту — слово значит играет роль структурного элемента предложения.
Если слово значит находится между частями бессоюзного сложного предложения, то оно также выделяется запятыми: Прозвенел звонок, значит, урок кончился; Не уберегли ребёнка, значит, пеняйте на самого себя».

А в параграфе 96 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина находим такую пару примеров: «Собираешься, значит, уезжать? — На небе собираются тучи, значит будет дождь (значит — союз)». Нетрудно заметить, что по справочнику Д. Э. Розенталя в последнем предложении следовало бы выделить слово значит запятыми: На небе собираются тучи, значит, будет дождь.

Разногласия в пунктуационных рекомендациях связаны с противоречивой грамматической трактовкой слова значит в лингвистических источниках, а эта трактовка, в свою очередь, связана с объективно наблюдаемыми языковыми процессами, в частности с развитием у слова значит союзной функции. Подробнее об этом можно прочитать в статье: Руднев Д. В., Друговейко-Должанская С. В. Союз или вводное слово? // #ТОТСБОРНИК: Сборник научных трудов по материалам Тотального диктанта. Вып. 4 / Отв. ред. Н. Б. Кошкарёва. — М., 2019. — С. 134–140. В финале статьи авторы отмечают: «Случай со словом значит ставит создателей пунктуационных правил перед сложной и интересной прагматической проблемой, пока не имеющей приемлемого решения».

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

В первом из приведенных примеров слово значит близко по смыслу к означает и не является вводным: Достославный — значит пользующийся доброй славой, прекрасной репутацией.

Обороты «по + имя собственное», указывающие, согласно чьему мнению, чьей точке зрения, теории и т. п. что-либо утверждается, обычно обособляются. Уточним, что обособляются они в случае, если играют роль вводных конструкций, указывающих на источник сообщения, например: По Аристотелю, не все блага равноценны: есть вспомогательные, а есть финальные. Однако такие обороты могут быть тесно связаны с какими-то словами в предложении — не только с глагольными формами, на что обычно указывают справочники, но и с существительными, о чём свидетельствуют Ваши примеры. В этих случаях оборот «по + имя собственное» не нуждается в обособлении. 

В приведенных примерах по Аристотелю играет роль несогласованного определения. Кстати, тот же смысл можно выразить с помощью прилагательного, т. е. согласованного определения: идеальное государство по Аристотелю = аристотелевское идеальное государство. Возможность такой замены служит дополнительным доказательством того, что по Аристотелю здесь не является вводной конструкцией.

Названия должностей в таких случаях обычно играют роль приложений при именах собственных, что не требует постановки знаков препинания (см. пункт 1 параграфа 63 «Полного академического справочника» под ред. В. В. Лопатина): Менеджер компании «Айдиго» Алёна провела презентацию по ассортименту продукции, а также раздала образцы специй и приправ. Представители компании Unilever Сергей и Александр провели презентацию и дегустацию своей продукции. Мы познакомились с новым менеджером Дмитрием Матюхиным. 

Обособление имен собственных в подобных контекстах допустимо в случаях, когда автор хочет особенным образом расставить акценты в высказывании. Например, если имена собственные находятся в середине предложения, они носить характер попутного замечания, поясняя название должности: Представители компании Unilever, Сергей и Александр, провели презентацию и дегустацию своей продукции. Имя собственное в конце предложения обособляется запятой или тире, если, по замыслу автора, логическое ударение падает и на название должности, и на имя собственное, в этом случае также играющее роль пояснения (без обособления логическое ударение падает только на имя собственное): Мы познакомились с новым менеджером — Дмитрием Матюхиным.

Полагаем, такое определение не соответствует действительности.

Воспользуйтесь этимологическими словарями, например словарем М. Фасмера, здесь.