Вопрос: Что это за формат данных и как его распарсить средствами PHP?

Лучший ответ: Хмм, как интересно. Наверное для начала стоит определиться с терминологией. В моем описании будет много тавтологий, но если подходить с точки зрения терминологии JS, то всё будет понятно:
1. Элемент это самостоятельная подстрока, при необходимости отделенная от другой запятой, и заключенная в кавычки если не описывает объект или массив,
2. Элемент начинающийся с фигурной скобки и ею заканчивающийся можно назвать объектом если первым элементом идет количество значений в виде числа, или массивом если вдобавок к первому условию также все дочерние его элементы описывают объекты (как бы это странно ни звучало). Также вторым элементом в массиве идет какой-то непонятный ключ фиксированной длины (36), который в подавляющем большинстве случаев одинаковый, но иногда все таки другой. Интрига.
3. Каждое значение описывается двумя элементами: первый описывает тип, второй - конкретное значение (извиняюсь за тавтологию). Типов существует 5: '#' - массив, 'S' - строка, 'N' - число, 'B' - boolean, 'D' - дата, unix timestamp.
4. Свойства объектов описываются так: первый объект описывает ключ свойства, а второй - его значение,Наколеночный алгоритм на JSinitial_string = `{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{14,{{"S","type"},{"S","order_change"}},{{"S","agent"},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{5,{{"S","id"},{"S","42318"}},{{"S","id_1c"},{"S","ПР10"}},{{"S","id_crm"},{"S","00-00164917"}},{{"S","name"},{"S","Иванова Тест"}},{{"S","contact"},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{3,{{"S","email"},{"S","K@mail.ru"}},{{"S","phone"},{"S","790000000"}},{{"S","contact_person"},{"S",""}}}}}}}},{{"S","id"},{"S","264762"}},{{"S","id_1c"},{"S","ЗА00-000000133586"}},{{"S","id_crm"},{"S","ЗА00-000000133586"}},{{"S","date"},{"S","2019-08-26"}},{{"S","time"},{"S","7:56:54"}},{{"S","amount"},{"N",215}},{{"S","delivery_date"},{"S","2019-08-26"}},{{"S","delivery_interval"},{"S","1-21-22"}},{{"S","items"},{"#",51e7a0d2-530b-11d4-b98a-008048da3034,{1,{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{9,{{"S","id_1c"},{"S","11014"}},{{"S","price"},{"N",215}},{{"S","quantity"},{"N",1}},{{"S","vat_rate"},{"N",0}},{{"S","name"},{"S","Вода 19л Классика"}},{{"S","discount_price"},{"S","0.00"}},{{"S","measure_code"},{"S","868"}},{{"S","measure_name"},{"S","бут"}},{{"S","type"},{"S","Товар"}}}}}}},{{"S","properties_values"},{"#",51e7a0d2-530b-11d4-b98a-008048da3034,{6,{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","Отменен"}},{{"S","value"},{"B",0}}}},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","ПометкаУдаления"}},{{"S","value"},{"B",0}}}},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","Финальный статус"}},{{"S","value"},{"B",0}}}},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","Статус заказа"}},{{"S","value"},{"S","[N] Принят"}}}},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","Статус заказа ИД"}},{{"S","value"},{"S","N"}}}},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","name"},{"S","Дата изменения статуса"}},{{"S","value"},{"D",20190826075719}}}}}}},{{"S","storage"},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{2,{{"S","id_1c"},{"S","2"}},{{"S","name"},{"S","Благодатская"}}}}},{{"S","forwarder_group"},{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,{0}}}}}`;

// для удобства меняем все скобки на квадратные и оборачиваем ключи кавычками
processed_string = initial_string
	.replace(/{/g, '[').replace(/}/g, ']')
	.replace(/[a-z0-9]{8}-[a-z0-9]{4}-[a-z0-9]{4}-[a-z0-9]{4}-[a-z0-9]{12}/gi, '"$&"');

main_sequence = eval(processed_string);

const parseThisFreakinOdinAssObject = (function() {
	const registered_types = [ '#', 'S', 'N', 'B', 'D' ];

	function processValue(type, value) {
		switch (type) {
			case 'S': {
				value = value.toString();
				break;
			}
			case 'N':
			case 'D': {
				value = Number(value);
				break;
			}
			case 'B': {
				value = Boolean(value);
				break;
			}
			case '#': {
				if (value) {
					const	declared_length = value[0],
							actual_length = value.length - 1;

					if (declared_length !== actual_length) {
						throw new Error(`The array actual length ${ actual_length } differs from declared length ${ declared_length }!`);
					}

					value = value.slice(1);
				} else {
					value = [];
				}
			}
		}

		return value;
	}

	return function parse(sequence) {
		const type = sequence[0];

		if (!registered_types.includes(type)) {
			throw new Error(`Type '${ type }' is not registered!'`);
		}

		// есл значение - массив, то пропускаем волшебный ключ
		let value = processValue(type, type === '#' ? sequence[2] : sequence[1]);

		if (value instanceof Array) {
			let temp_value;

			// если дочерний элемент также массив, то значит текущий элемент не объект, а массив
			if (value[0] && value[0][0] === '#') {
				temp_value = [];

				value.forEach(entry => {
					temp_value.push( parse(entry) );
				});
			} else {
				temp_value = {};
				value.forEach(entry => {
					temp_value[ parse(entry[0]) ] = parse(entry[1]);
				});
			}

			value = temp_value;
		}

		return value;
	}
})();

parseThisFreakinOdinAssObject(main_sequence);JSON-представление данных из примера{
    "type": "order_change",
    "agent": {
        "id": "42318",
        "id_1c": "ПР10",
        "id_crm": "00-00164917",
        "name": "Иванова Тест",
        "contact": {
            "email": "K@mail.ru",
            "phone": "790000000",
            "contact_person": ""
        }
    },
    "id": "264762",
    "id_1c": "ЗА00-000000133586",
    "id_crm": "ЗА00-000000133586",
    "date": "2019-08-26",
    "time": "7:56:54",
    "amount": 215,
    "delivery_date": "2019-08-26",
    "delivery_interval": "1-21-22",
    "items": [
        {
            "id_1c": "11014",
            "price": 215,
            "quantity": 1,
            "vat_rate": 0,
            "name": "Вода 19л Классика",
            "discount_price": "0.00",
            "measure_code": "868",
            "measure_name": "бут",
            "type": "Товар"
        }
    ],
    "properties_values": [
        {
            "name": "Отменен",
            "value": false
        },
        {
            "name": "ПометкаУдаления",
            "value": false
        },
        {
            "name": "Финальный статус",
            "value": false
        },
        {
            "name": "Статус заказа",
            "value": "[N] Принят"
        },
        {
            "name": "Статус заказа ИД",
            "value": "N"
        },
        {
            "name": "Дата изменения статуса",
            "value": 20190826075719
        }
    ],
    "storage": {
        "id_1c": "2",
        "name": "Благодатская"
    },
    "forwarder_group": {}
}

Худший ответ: UID типа 4238019d-7e49-4fc9-91db-b6b951d5cf8e   преврати в строку (кавычки) и попробуй как JSON