É 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: link