Правильно: согласно статье, согласно параграфу.
Написание регулируется правилом о правописании суффиксов причастий.
В этих примерах деепричастный оборот имеет значение образа действия, тесно связан по содержанию со сказуемым и образует смысловой центр высказывания. Подобные деепричастные обороты не обособляются (см. примечание 1 к параграфу 20.4 справочника по пунктуации Д. Э. Розенталя): необходимо использовать не касаясь руками; ...позволяет пользоваться тряпкой не касаясь руками (важно не то, что тряпкой пользуются, а то, каким образом пользуются).
Запятая перед первым тире не нужна, так как содержащее дополнительные сведения сочетание зачастую без предупреждения, оформленное в виде вставки, относится к глаголу появлялись: Когда они появлялись — зачастую без предупреждения, — отец всегда встречал их радушно и приглашал в дом. Об особенностях сочетания запятых и тире при вставных конструкциях см. примечание 4 к параграфу 26.2 справочника по пунктуации Д. Э. Розенталя.
Ваше предположение верно: по имени Валя — приложение. Такие приложения, согласно параграфу 64 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина (М., 2006 и след.), обособляются, но могут и, согласно примечанию 1 к этому параграфу, «не обособляться, если они имеют основное, выделительное значение, т. е. не являются уточнением или пояснением впереди стоящего определяемого слова: Завел он себе медвежонка по имени Яша».
Двоеточие после слова сообщение нужно (см. примечание к параграфу 50 справочника по пунктуации Д. Э. Розенталя).
Запятая не ставится. См. о таких случаях «Справочник по русскому языку. Пунктуация» Д. Э. Розенталя, примечание 1 к параграфу 48.
Надпись представлена как подлинное выражение, включённое в текст, поэтому её точно нужно заключить в кавычки и начать с прописной буквы. Другой вопрос, требуется ли перед ней двоеточие. В примечании к параграфу 50 справочника по пунктуации Д. Э. Розенталя приводятся, с одной стороны, примеры типа Он вспомнил пословицу «За двумя зайцами погонишься — ни одного не поймаешь» и отказался от первоначального плана, с другой — примеры типа Мимо станции проносились скорые поезда с табличками на вагонах: «Москва — Владивосток». Там же отмечено, что двоеточие ставится, если перед подлинным выражением имеются слова предложение, выражение, надпись и т. п. Но, судя по всему, дело в другом: в примерах с двоеточием подлинное выражение, включённое в текст, завершает собой предложение, в примерах без двоеточия — находится в середине предложения. Таким образом, корректно будет такое оформление: На столе стояла кружка с надписью: «Маме», но Кружку с надписью «Маме» кто-то убрал со стола.