Quando alguém diz que determinada linguagem é (ou não é) OOP, primeiro devemos nos perguntar: de qual OOP estamos falando?

Pois é. Não existe uma definição única, canônica, oficial e universalmente aceita sobre o que é orientação a objeto. No fundo ninguém concorda.

O que temos são escolas, ou se preferir, vertentes. No link já indicado pelo Maniero tem uma análise bem detalhada, sugiro que leia tudo pra entender o histórico e as contradições que as pessoas infelizmente não param mais pra pensar a respeito. Mas de forma bem resumida, podemos dizer que as principais vertentes são a de Alan Kay e Bjarne Stroustrup:

O primeiro é "só" o cara que cunhou o termo "orientação a objeto" (veja aqui e aqui o que ele mesmo tem a dizer sobre isso) e o segundo criou um tal de C++, acho que vc já ouviu falar :-)

Bom, o link já indicado tem todos os detalhes, mas só pra resumir, uma das vertentes é que para ser OOP basta seguir os 3 pilares (encapsulamento, herança e polimorfismo - há vertentes que incluem outros, mas não vamos nos alongar). Note que não é obrigatório usar classes, já que elas são apenas um mecanismo que facilita tudo isso, mas nem de longe é pré-requisito. JavaScript, por exemplo, usa protótipos (até existe a palavra-chave class, mas é só um syntax sugar, pois debaixo dos panos continua usando protótipos). Até mesmo em C é possível "programar orientado a objeto" (ou seja, seguindo os 3 pilares, caso vc siga tal vertente).

Por isso, quando dizemos que uma linguagem é ou não OOP, primeiro temos que saber de qual escola estamos falando. E mesmo assim é complicado, porque a maioria das linguagens - senão todas - hoje em dia são híbridas, contendo um pouco de cada paradigma. Dizer que ela é somente uma coisa costuma ser uma simplificação, muitas vezes até marketeira.

O próprio FAQ oficial da linguagem Go possui a pergunta "Go é orientada a objeto?" e a resposta é "Sim e não".

Objeto

Quanto à definição de objeto, ela pode ser tão confusa quanto a de OOP. O Maniero também já colocou o link, no qual podemos ver que a definição de objeto é bem mais ampla do que costumamos ver por aí. Praticamente qualquer coisa (variável, estrutura, função/método, etc), qualquer região da memória que contenha um valor e possa ser acessada e manipulada pode ser um objeto.

O problema é que cada linguagem também costuma ter sua própria definição, muitas vezes mais restrita que o conceito geral. Por exemplo, em JavaScript a MDN define como "uma coleção de propriedades". Em Python, um objeto é uma "abstração para dados". Em outras linguagens, é "uma instância de uma classe". Em C11, na seção 3.15, objeto é "uma região de armazenamento de dados no ambiente de execução, cujo conteúdo pode representar valores".

Então tem que ver qual a definição que Go dá para "objetos" (mas tecnicamente falando, ela tem sim).