Интересно, что есть гипотезы, что искусство именно палеолита - еще не вполне искусство (не в нашей современной оценке, а в причинах и механизмах своего появления), а сам факт создания изображений возможно относится еще к сфере филогенеза, а не истории. Религия же феномен полностью социально-исторический, ergo в палеолите ее и духу быть в таком разе не могло, как и искусства в нынешнем понимании. Долго копать по этому вопросу тут не стану (можно открыть отдельную тему), за себя скажу, что мне доводы, приведенные в пользу такой гипотезы* кажутся убедительными, и я бы в палеолит с религиями и искусствами не лазил. Нижнюю границу имеет смысл провести по "мезолиту".
* см. например П.А. Куценков "Начало".