aタグの中にPHPを入れるとなぜか正常に動作しない...

その部分だけを見れば間違いではないかもしれませんが、
例えば、下記みたいにして、式ではなく文字として代入してたりすると思い通りにはなりません。

<?php
$page = '123';
$hoge = '<a href="http://xxx/xxx/?page=<?php print($page + 1); ?>">次のページへ</a>';
print $hoge;

例えば、下記みたいにして、以下同文

<?php
print<<<EOT
<a href="http://xxx/xxx/?page=<?php print($page + 1); ?>">次のページへ</a>
EOT;

例えば・・・例えば・・・ほかにもいろいろ考えられますが、
書き間違いによる文法エラーを除けば、
エラーの原因は、エラー発生箇所以外にある場合がほとんどです。

そのため、問題解決するためには、下記のような情報が必須です。
・具体的にどのような状態になっているかを説明した図や文章
・本当はどのような状態にしたいのかを説明した図や文章
・エラーが発生するコード全部
　（自己判断で部分的に見当がつくくらいなら質問する必要はまずもって無い）
・エラーメッセージが出ている場合はエラーメッセージと発生箇所

これからも多数の質問をすることでしょうから、覚えておいてください。


さて、本題に戻って、ここからは過去の質問から想像して書きますが、
多分下記のようにすれば良いでしょう。

<?php
$page = '123';
$hoge = '<a href="http://xxx/xxx/?page=' . ($page + 1) . '">次のページへ</a>';
print $hoge;

phpの学習を進める前に、
演算子には優先順位があるということをまずは理解してください。
http://php.net/manual/ja/language.operators.precedence.php

もしそのままブラウザに送信されているなら、これをチェック

• ドキュメントの拡張子がhtml（phpとかcgiになっていない）
• CGIとして動作していない
• １行目に「#! /usr/local/bin/php」というような記述が無い