Илья

Метод getLicense сделайте protected и для теста наследуйтесь от основного класса и подменяйте метод getLicense.
Тогда вообще ничего переписывать не придется.

public function testCase()
{
    $mockObject = $this->createMock(NeedClass::class);
    // чем это принципиально отличается от мока с точки зрения теста - непонятно
    $mockObject = new class extends NeedClass {
        protected function getLicense(array $categories)
        {
            return 'need license';
        }
    };

    $this->assertEqual($mockObject->getPaidShops(), 'actual value');
}

Как вариант, можно переписать код, чтобы в тестируемый класс в конструктор передавался APIService (а не создавался напрямую в методе), и в юнит тестах в конструктор передавать мок этого класса с данными которые подкинутся в getLicenses из сервис провайдера

Ну вообще так и надо сделать, DI все дела :)