Это так называемое эллиптическое предложение. Эллиптические предложения представляют собой особую разновидность неполных предложений; в отличие от обычных неполных предложений, они сохраняют смысловую достаточность даже будучи вырванными из контекста.

В самом деле: предложение Лесникова вне контекста производит странное впечатление. А вот в контексте, из которого оно взято, оно вполне осмысленно, потому что контекст дополняет все то, что в нем опущено:

- Ты лесникова дочь?

- Лесникова. (И. С. Тургенев. Записки охотника)

Таковы обычные неполные предложения.

В приведенном вами примере опущена вся грамматическая основа, но он и вне контекста вполне понятен.

О наличии грамматической основы свидетельствуют формы косвенных падежей: дательного (работнику) и винительного (зарплату). Косвенный падеж сам по себе, «ниоткуда», появиться не может: это всегда зависимая форма. Следовательно, подразумевается главный член, который требует, чтобы зависимые от него дополнения приняли формы именно этих падежей. Например, Каждому работнику следует назначить достойную зарплату; Каждому работнику назначьте достойную зарплату. В первом случае перед нами безличное предложение, во втором — определенно-личное. Возможны и другие способы восстановления главного члена (= грамматической основы), но в любом случае он есть.

Не и ни выбраны верно, но обратите внимание на их слитное/раздельное написание: Царила полная тишина, ниоткуда ни звука, сколько я ни прислушивался к незнакомому месту.

Запятая не нужна.

Верно: появиться ниоткуда. У Бродского: "Ниоткуда с любовью...".

Такие сочетания возможны.