É preciso definir a chave estrangeira na relação, então fica assim:
public function categoria(){ return $this->belongsTo('estoque\Categoria', 'categoria_id'); }
Então só acessar como objeto:
<td> {{$p->categoria->nome}} <td>
Perguntei no SOen: linklink
Perguntei no SOen: link