It kind of irritates me that Kate doesn’t have a builtin functionality to move cursor to the next/previous paragraph. Fortunately, as with most KDE SC applications, Kate is extendable with custom scripts. So here’s my solution for the mentioned problem.

/* kate-script
 * author: Dzikri Aziz 
 * license: GPLv2
 * revision: 3
 * kate-version: 3.4
 * type: commands
 * functions: jumpUp, jumpDown
 *
 * Move cursor to next/previous paragraph
 */

function jumpDown() {
  return _jump();
}


function jumpUp() {
  return _jump( true );
}


function action( cmd ) {
  var a = new Object();
  if ( cmd == 'jumpUp' ) {
    a.text = i18n('Move cursor to previous paragraph');
    a.shortcut = 'Alt+Up';
    a.icon = "";
    a.category = "";
    a.interactive = false;
  }
  else if ( cmd == 'jumpDown' ) {
    a.text = i18n('Move cursor to next paragraph');
    a.shortcut = 'Alt+Down';
    a.icon = "";
    a.category = "";
    a.interactive = false;
  }

  return a;
}


function help( cmd ) {
  if (cmd == 'jumpUp') {
    return i18n('Move cursor to previous paragraph');
  }
  else if (cmd == 'jumpDown') {
    return i18n('Move cursor to next paragraph');
  }
}


function _jump( up ) {
  var init   = curPos = view.cursorPosition().line,
      lines  = document.lines(),
      target;

  if ( document.firstColumn(curPos) == -1 )
    curPos = document.prevNonEmptyLine(curPos);

  if ( up === true ) {
    target = 0;
    while ( curPos-- > 0 ) {
      if ( document.firstColumn(curPos) == -1 && document.nextNonEmptyLine(curPos) != init ) {
        target = document.nextNonEmptyLine(curPos);
        break;
      }
    }
  }

  else {
    lines--;
    target = lines;
    while ( curPos++ < lines ) {
      if ( document.firstColumn(curPos) == -1 && document.nextNonEmptyLine(curPos) != init ) {
        target = document.nextNonEmptyLine(curPos);
        break;
      }
    }
  }

  view.setCursorPosition(target, 0);
}

Save this script as jump.js inside katepart directory in your KDE user directory, eg: $KDEHOME/share/apps/katepart/script (just create the sub-directories if they don't exist yet) and relaunch Kate. Now you can move the cursor to the next paragraph by pressing Alt+Up or the previous one by pressing Alt+Down. You can freely customize the shortcut from Settings » Configure Shortcuts.

Any improvements are welcome!

As a bonus, here's the scripting guide I printed from Google cache.