Where does $\forall xP(x,x)\land\forall x\forall y( P(x,y)\rightarrow\forall z( P(x,z)\land P(y,z) ) )\rightarrow \exists x\forall yP(y,x)$ not hold? 
Let's have a first-order language with a categorical symbol $P(x,y)$.
  Define the statement: $$\phi\equiv \forall xP(x,x)\land \forall
 x\forall y( P(x,y)\rightarrow \forall z( P(x,z)\land P(y,z) )
)\rightarrow \exists x\forall yP(y,x)$$
Formulate an interpretation that is not a model of $\phi$.

I cannot see why that wouldn't hold anywhere... Seems to me that it is true in every interpretation.
Because of the second condition of the implication and setting $y=x$, since the first condition $\forall xP(x,x)$ holds, we would obtain that every element would be related though $P$ with every other, that is $\forall x\forall yP(x,y)$ holds under the assumptions of the implication. So, in which interpretation would the implication not hold ?
 A: You are right: it is valid.
Here is a proof with Tableau:
1) $∀xP(x,x) ∧ ∀x∀y(P(x,y) → ∀z(P(x,z)∧P(y,z)))$ --- premise
2) $\lnot ∃x∀yP(y,x)$ --- negation of the conclusion
3) $\lnot ∀yP(y,a)$ --- from 2)
4) $\lnot P(b,a)$ --- from 3) : $b$ new
5) $∀xP(x,x)$ --- from 1)
6) $∀x∀y(P(x,y) → ∀z(P(x,z)∧P(y,z)))$ --- from 1)
7) $P(b,b)$ --- from 5)
8) $P(b,b) → ∀z(P(b,z)∧P(b,z))$ --- from 6)
9a) $\lnot P(b,b)$ --- left branch from 8): it closes with 7)
9b) $∀z(P(b,z)∧P(b,z))$ --- right branch from 8)
10) $P(b,a)$ --- from 9b): it closes with 4).
A: The only countermodel is an empty one.
If you assume that there exists at least one object in the domain, then it is valid. The following proof is made in Fitch, which does assume that there is at least one object. You can see that assumption being used on line 5:

A: $\def\fitch#1#2{~~\begin{array}{|l}#1\\\hline #2\end{array}}$
The statement holds using intuitionistic first-order logic as long we disallow an empty domain.
$$\fitch{(\forall x~P(x,x))\wedge(\forall x~\forall y~(P(x,y)\to\forall z~(P(x,z)\wedge P(y,z))))}{\forall x~P(x,x)\\\forall x~\forall y~(P(x,y)\to\forall z~(P(x,z)\wedge P(y,z)))\\\fitch{[a]}{P(a,a)\\\forall y~(P(a,y)\to\forall z~(P(a,z)\wedge P(y,z)))\\P(a,a)\to\forall z~(P(a,z)\wedge P(a,z))\\\forall z~(P(a,z)\wedge P(a,z))\\\fitch{[b]}{P(a,b)\wedge P(a,b)\\P(a,b)}\\\forall y~P(a,y)}\\\forall x~\forall y~P(x,y)\\\exists x~\forall y~P(x,y)\qquad\text{if the domain is not empty}}$$
