So here we are,
The package provided in (X)ubuntu 13.4 is this one : "GNU Emacs 24.2.1 (i686-pc-linux-gnu, GTK+ Version 3.6.4) of 2013-04-09 on komainu, modified by Debian".
I tried "C-h f url-encode-url RET" but wihout the expected results.
I tried to find something with google and I seems that the version of Emacs must greater than 24.2.1.
I used the PAA for Damien CASSOU, install Emacs 24.3.1. The command 'url-encode-url' was listed in.
I tried both org-rss-export-as/to-rss and it worked. I also tested the org-publish-project-alist approach with success.
So my problem comes from the Emacs version. Thanks for your help!