コードと解説

関連記事に置き換えるものを考えてますので「single.php」に記述します。

single.php
<?php
$cats = get_the_category();
//記事が２つ以上の場合表示
if(($cats[0]->count) > 1 ):
?>
<div>
  <h4>その他の記事</h4>
  <ul>
  <?php
    $posts = get_posts('numberposts=5&exclude='.get_the_ID().'&category='.$cats[0]->term_id);
    if($posts): foreach($posts as $post) : setup_postdata($post);
  ?>
  <li><a href="<?php the_permalink() ?>"><?php the_title(); ?></a></li>
  <?php endforeach; endif; ?>
  </ul>
</div>
<?php endif; ?>

「get_the_category」で所属しているカテゴリー情報を取得することができます。
この中の[count]がそのカテゴリーに所属している記事の数なので、この数が1より大きい（2以上）の場合のみ表示します。

「get_posts」で取得する記事の条件を指定します。

numberposts表示する記事の数
exclude除外する記事のID
categoryカテゴリー指定

excludeに現在記事のID（get_the_ID）、categoryには所属しているカテゴリーID（$cats[0]->term_id）を指定します。
あとはいつものようにループして表示させるだけですね。